CF721E.Road to Home

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.

最近，学生丹尼尔从电车站步行回家，走的是一条长度为 $L$ 的笔直道路。电车站位于 $x = 0$ 处，而丹尼尔的家位于 $x = L$ 处。丹尼尔以恒定速度从 $x = 0$ 向 $x = L$ 行进，且不改变行进方向。

道路上共有 $n$ 盏路灯，每盏灯照亮道路的一个连续区间。这 $n$ 个被照亮的区间两两互不相交（即无公共点）。

丹尼尔酷爱唱歌，因此希望在步行途中反复演唱他最喜爱的歌曲。由于未被照亮的路段令他感到害怕，他仅在经过被照亮的路段时才唱歌。

丹尼尔演唱一次该歌曲需走过距离 $p$。若演唱过程中所经过的路段并非完全处于被照亮区间内，则他不能开始下一次演唱。此外，若丹尼尔在两次演唱之间曾暂停，则他必须至少走过长度为 $t$ 的路段后，才能重新开始演唱。形式化地：

1. 丹尼尔仅可在点 $x$ 处开始一次演唱，当且仅当区间 $[x,\, x + p]$ 上的每一个点均被照亮；
2. 若丹尼尔在点 $x + p$ 处结束本次演唱，则下一次演唱只能在点 $y$ 处开始，其中 $y = x + p$ 或 $y \ge x + p + t$，且须满足第 1 条所述条件。

图中蓝色半圆表示演唱行为。请注意：丹尼尔在暂停演唱后，必须至少走过长度为 $t$ 的路段才可再次开始演唱。

请确定：丹尼尔从 $x = 0$ 走到 $x = L$ 的整个过程中，最多能演唱他最喜爱的歌曲多少次。

请注意：丹尼尔不会中断一次正在进行的演唱；也就是说，一旦他开始演唱，就一定会持续演唱，直至从起始点起走过长度为 $p$ 的路段后才结束。

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

输入的第一行包含四个整数 $L$、$n$、$p$ 和 $t$（$1 ≤ L ≤ 10^9$，$0 ≤ n ≤ 100\,000$，$1 ≤ p ≤ 10^9$，$1 ≤ t ≤ 10^9$）——分别表示丹尼尔路径的长度、道路上路灯的数量、丹尼尔完成一次表演所经过的距离，以及暂停所需的最小距离。

接下来的 $n$ 行描述了由路灯照亮的线段。第 $i$ 行包含两个整数 $l_i$、$r_i$（$0 ≤ l_i < r_i ≤ L$），表示第 $i$ 盏路灯所照亮线段的两个端点。保证任意两个线段互不相交、互不嵌套，且互不接触。这些线段按从左到右的顺序给出。

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

输出唯一的整数——丹尼尔最喜爱的歌曲在从 $x = 0$ 到 $x = L$ 的路径上最多可播放的次数。

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

第一个样例对应题目描述中的图片。