1750: Road to Home
Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
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,
- Danil can start single performance at a point x only if every point of segment [x,x+p] is lightened;
- 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≤109, 0≤n≤100000, 1≤p≤109, 1≤t≤109)− 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 li,ri (0≤li<ri≤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.
17 2 2 6
0 9
13 17
5
12 2 2 2
0 5
6 11
4
12 2 2 4
0 5
6 11
3
The first sample case is just about corresponding to the picture from the statement.