CF721E Road to Home

有一天，学生 Danil 从电车站回家，走在一条长度为 $L$ 的直路上。电车站位于 $x=0$ 点，而 Danil 家在 $x=L$ 点。Danil 以恒定速度从 $x=0$ 走到 $x=L$，并且不改变前进方向。 道路上共有 $n$ 个路灯，每盏路灯照亮道路上一段连续的区间。所有 $n$ 个被照亮的区间互不相交，也没有重叠或接触点。 Danil 喜欢唱他最喜欢的歌曲，因此他想在回家路上一遍又一遍地唱这首歌。由于未被照亮的路段让他感到害怕，所以他只有在经过被照亮的路段时才会唱歌。 Danil 每次演唱这首歌时会经过一段长度为 $p$ 的路。只有当一首歌所经过的整段路都被照亮时，他才能开始唱歌。如果 Danil 两次演唱之间有停顿，则他在没有连续走过至少 $t$ 的距离前不会再次演唱。形式化定义如下： 1. Danil 只有在当前点 $x$ 开始到 $[x, x+p]$ 区间内的所有点都被照亮时，才能开始一次演唱； 2. 如果 Danil 在 $x+p$ 处完成了一次演唱，则下一次演唱只能从 $y$ 开始，其中 $y=x+p$ 或 $y \geq x+p+t$，并且需满足条件 1。  蓝色半圆标记了演唱的位置。请注意，只要 Danil 在两次演唱之间有停顿，他就至少有长度为 $t$ 的一段路没有在唱歌。 请你计算 Danil 从 $x=0$ 到 $x=L$ 的过程中最多可以唱多少遍他喜欢的歌。

输入的第一行包含四个整数 $L$、$n$、$p$ 和 $t$（$1 \leq L \leq 10^{9}$，$0 \leq n \leq 100000$，$1 \leq p \leq 10^{9}$，$1 \leq t \leq 10^{9}$），分别表示 Danil 的路线长度、路灯数量、每次演唱时经过的路程长度，以及两次演唱间的最小停顿距离。 接下来的 $n$ 行，每行包含两个整数 $l_i,r_i$（$0 \leq l_i < r_i \leq L$），表示第 $i$ 个路灯照亮的区间的端点。保证没有两个区间有交集、包含或接触。区间按照从左到右的顺序给出。

输出一个整数，表示 Danil 在回家路上最多能唱多少遍他喜欢的歌。

第一个样例即为题干图片所对应的场景。 由 ChatGPT 5 翻译