Road to Home

题意翻译

最近有一个学生Danil正在通过一条长度为$L$的笔直道路从电车站回家。这个站点位于点$x=0$，但是Danil的家——在点$x=L$。Danil以恒定速度从$x=0$到$x=L$走动，并且过程中不改变方向。 路上有n盏路灯，每盏路灯照亮路段的一些连续路段。这n盏灯照亮的路段没有公共点。 Danil喜欢唱歌，因此他想在他散步时一遍又一遍地唱出他最喜欢的歌。一旦他被没有照亮的路段吓到了，就只会在在经过被照亮的部分时才会唱歌。 Danil表演他最喜欢的歌曲时会经过$p$个距离。如果表演过程中经过的路段没有被照亮，他就无法开始另一场表演。此外，如果Danil在两场表演之间停顿了一会，并且经过了一段长度至少为t的路时，他会停止表演。从形式上看： 1. 只有当经过一段被照亮的路段$[x,x+p]$时，Danil才能在$x$点开始表演一曲。 2. 如果Danil在$x+p$点完成表演，那么下一个表演只能在$y$点开始，使得$y=x+p$或者$y \ge x+p+t$满足第1点的声明。 蓝色的半圆表示表演的部分。请注意，就在Danil暂停表演之后，他还没有在经过一段长度至少为t的路上唱歌。 确定Danil在从$x=0$到$x=L$的步行过程中可以表演他最喜欢的歌曲的次数。 请注意，Danil并没有停止一个表演，因此，当经过一段从表演开始点至少长度为p的路时，他完成了唱歌，并开始了另一次歌唱。

题目描述

Once Danil the student was returning home from tram stop lately by straight road of length $ L $ . The stop is located at the point $ x=0 $ , but the Danil's home — at the point $ x=L $ . Danil goes from $ x=0 $ to $ x=L $ with a constant speed and does not change direction of movement. There are $ n $ street lights at the road, each of which lights some continuous segment of the road. All of the $ n $ lightened segments do not share common points. Danil loves to sing, thus he wants to sing his favourite song over and over again during his walk. As soon as non-lightened segments of the road scare him, he sings only when he goes through the lightened segments. Danil passes distance $ p $ while performing his favourite song once. Danil can't start another performance if the segment passed while performing is not fully lightened. Moreover, if Danil has taken a pause between two performances, he is not performing while not having passed a segment of length at least $ t $ . Formally, 1. Danil can start single performance at a point $ x $ only if every point of segment $ [x,x+p] $ is lightened; 2. If Danil has finished performing at a point $ x+p $ , then the next performance can be started only at a point $ y $ such that $ y=x+p $ or $ y>=x+p+t $ satisfying the statement under the point $ 1 $ . Blue half-circles denote performances. Please note that just after Danil has taken a pause in performing, he has not sang for a path of length of at least $ t $ .Determine how many times Danil can perform his favourite song during his walk from $ x=0 $ to $ x=L $ . Please note that Danil does not break a single performance, thus, started singing another time, he finishes singing when having a segment of length of $ p $ passed from the performance start point.

输入输出格式

输入格式

The first line of the input contains four integers $ L $ , $ n $ , $ p $ and $ t $ ( $ 1<=L<=10^{9} $ , $ 0<=n<=100000 $ , $ 1<=p<=10^{9} $ , $ 1<=t<=10^{9} $ ) — the length of the Danil's path, the number of street lights at the road, the distance Danil passes while doing single performance and the minimum distance of pause respectively. The next $ n $ lines describe segments lightened by street lights. $ i $ -th of them contains two integers $ l_{i},r_{i} $ ( $ 0<=l_{i}&lt;r_{i}<=L $ ) — the endpoints of the segment lightened by $ i $ -th street light. It is guaranteed that no two segments are intersecting, nesting, or touching each other. The segments are given in the order from left to right.

输出格式

Print the only integer — the maximum number of performances of Danil's favourite song on the path from $ x=0 $ to $ x=L $ .

输入输出样例

输入样例 #1

17 2 2 6
0 9
13 17

输出样例 #1

5

输入样例 #2

12 2 2 2
0 5
6 11

输出样例 #2

4

输入样例 #3

12 2 2 4
0 5
6 11

输出样例 #3

3

说明

The first sample case is just about corresponding to the picture from the statement.