← 返回题目列表

Codeforces · 721/E

E. 回家之路

中文机器翻译题面 查看原题

有一次,丹尼尔最近从电车站沿长度为 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

注意

第一个示例案例与声明中的图片几乎对应。