问题文

IOI 国有两个城镇，分别编号为 1 和 2。

这些城镇共举办了 N 个事件。这些事件从 1 到 N 进行编号。事件 i（1 ≤ i ≤ N）在城镇 Pi 中举行，举办时间从时刻 Si + 0.1 到时刻 Si + 0.9。其中 Si 是一个整数。为了参加事件 i，JOI 必须在时刻 Si + 0.1 到 Si + 0.9 期间一直待在城镇 Pi。

JOI 决定进行事件巡回。在事件巡回中，JOI 可以参加多个事件，如果需要的话，还可以在城镇之间移动。JOI 在时刻 0 开始进行事件巡回。这时，他可以从任意一个城镇开始。

JOI 可以双向移动城镇 1 和城镇 2 之间。移动两个城镇所需的时间是 JOI 参加的事件数量 j，即 D + K × j。

给定有关事件和城镇移动的信息，请编写程序来确定 JOI 可以参加的事件数量的最大值。

约束条件

• 1 ≤ N ≤ 200,000。
• 1 ≤ D ≤ $10^{12}$。
• 0 ≤ K ≤ $10^{12}$。
• 1 ≤ Pi ≤ 2（1 ≤ i ≤ N）。
• 1 ≤ Si ≤ $10^{12}$（1 ≤ i ≤ N）。
• Si ≠ Sj（1 ≤ i < j ≤ N）。
• 输入的值均为整数。

小任务

1. （8 分）K = 0，N ≤ 20。
2. （11 分）K = 0，N ≤ 4,000。
3. （24 分）K = 0。
4. （12 分）N ≤ 160。
5. （23 分）N ≤ 4,000。
6. （22 分）无附加约束条件。

输入

输入从标准输入中以以下格式给出。

N D K P1 S1 P2 S2 ⋮ PN SN

输出

将 JOI 可以参加的事件数量的最大值以一行输出到标准输出中。

输入示例 1

5 3 0
1 1
1 2
1 10
2 5
2 6

输出示例 1

4

例如，通过以下行动，JOI 可以参加 4 个事件：

1. 在时刻 0，JOI 在城镇 1。
2. 在时刻 1.1 到时刻 1.9，JOI 在城镇 1 参加事件 1。
3. 在时刻 2.1 到时刻 2.9，JOI 在城镇 1 参加事件 2。
4. 在时刻 3 到时刻 6，用时 3（等于 D + K × 2）从城镇 1 移动到城镇 2。
5. 在时刻 6.1 到时刻 6.9，JOI 在城镇 2 参加事件 5。
6. 在时刻 7 到时刻 10，用时 3（等于 D + K × 3）从城镇 2 移动到城镇 1。
7. 在时刻 10.1 到时刻 10.9，JOI 在城镇 1 参加事件 3。

由于无论如何行动，JOI 最多只能参加 5 个事件，因此输出 4。

该输入示例满足所有小任务的约束条件。

输入示例 2

7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25

输出示例 2

6

例如，通过以下行动，JOI 可以参加 6 个事件：

1. 在时刻 0，JOI 在城镇 2。
2. 在时刻 2.1 到时刻 2.9，JOI 在城镇 2 参加事件 1。
3. 在时刻 3 到时刻 8，用时 5（等于 D + K × 1）从城镇 2 移动到城镇 1。
4. 在时刻 8.1 到时刻 8.9，JOI 在城镇 1 参加事件 2。
5. 在时刻 11.1 到时刻 11.9，JOI 在城镇 1 参加事件 4。
6. 在时刻 12 到时刻 23，用时 11（等于 D + K × 3）从城镇 1 移动到城镇 2。
7. 在时刻 23.1 到时刻 23.9，JOI 在城镇 2 参加事件 5。
8. 在时刻 24.1 到时刻 24.9，JOI 在城镇 2 参加事件 6。
9. 在时刻 25.1 到时刻 25.9，JOI 在城镇 2 参加事件 7。

由于无论如何行动，JOI 最多只能参加 7 个事件，因此输出 6。

该输入示例满足小任务 4、5 和 6 的约束条件。

输入示例 3

12 153 0
1 155
2 861
1 646
1 218
2 450
2 56
1 932
2 295
2 863
1 612
2 38
2 768

输出示例 3

8

该输入示例满足所有小任务的约束条件。

输入示例 4

15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575

输出示例 4

11

该输入示例满足小任务 4、5 和 6 的约束条件。