Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC).
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Road to Home

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOnce 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.

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.

Input

The first line of the input contains four integers *L*, *n*, *p* and *t* (1 ≤ *L* ≤ 10^{9}, 0 ≤ *n* ≤ 100 000, 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} < *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.

Output

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

Examples

Input

17 2 2 6

0 9

13 17

Output

5

Input

12 2 2 2

0 5

6 11

Output

4

Input

12 2 2 4

0 5

6 11

Output

3

Note

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/02/2021 19:55:36 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|