有一次,丹尼尔最近从电车站沿长度为 L 的直道从电车站回家。车站位于点 x = 0,但丹尼尔的家位于点 x = L。丹尼尔以恒定速度从 x = 0 到 x = L,并且不改变运动方向。
道路上有 n 个路灯,每个路灯照亮道路的一些连续路段。所有 n 个变亮的线段都不共享公共点。
丹尼尔喜欢唱歌,因此他想在散步时一遍又一遍地唱他最喜欢的歌曲。一旦没有灯光的路段吓到了他,他只有在经过有灯光的路段时才会唱歌。
丹尼尔在表演一次他最喜欢的歌曲时经过了距离 p。如果表演时经过的片段没有完全变亮,丹尼尔就无法开始另一场表演。此外,如果丹尼尔在两次表演之间暂停,那么他在没有经过长度至少为 t 的片段时就不算表演。正式地,
1、只有线段[x, x + p]的每个点都变亮时,Danil才能在x点开始单次表演;
2. 如果 Danil 在 x + p 点表演完毕,则只能在 y 点开始下一次表演,使得 y = x + p 或 y ≥ x + p + t 满足点 1 下的陈述。
蓝色半圆圈表示性能。请注意,丹尼尔在表演暂停后,他在至少 t 长度的路径中没有唱歌。
确定 Danil 在从 x = 0 到 x = L 的步行过程中可以演奏他最喜欢的歌曲多少次。
请注意,Danil 不会中断一次表演,因此,又开始唱歌,当从表演起点经过一段长度为 p 的片段时,他结束唱歌。
输入
输入的第一行包含四个整数 L、n、p 和 t (1 ≤ L ≤ 109, 0 ≤ n ≤ 100 000, 1 ≤ p ≤ 109, 1 ≤ t ≤ 109)——Danil 路径的长度、路上路灯的数量、Danil 在单次表演时经过的距离以及分别暂停。
接下来的 n 行描述了路灯照亮的部分。其中第 i 个包含两个整数 li, ri (0 ≤ li < ri ≤ L) - 第 i 个路灯照亮的路段的端点。确保没有两个线段相交、嵌套或接触。这些段按从左到右的顺序给出。
输出
打印唯一的整数——从 x = 0 到 x = L 的路径上 Danil 最喜欢的歌曲的最大演奏次数。
示例
输入 #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
注意
第一个示例案例与声明中的图片几乎对应。