题目描述

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

在这些城镇中，总共将举办 $N$ 个活动。这些活动分别编号为 1 到 $N$。活动 $i$（$1 \le i \le N$）在城镇 $P_i$ 举办，举办时间为从时刻 $S_i + 0.1$ 到时刻 $S_i + 0.9$。其中，$S_i$ 为整数。JOI 君若要参加活动 $i$，则必须在时间段 $S_i + 0.1$ 至 $S_i + 0.9$ 内始终位于城镇 $P_i$。

JOI 君决定进行一次活动巡游。在巡游过程中，他可以参加若干个活动，必要时也可在城镇之间移动。JOI 君从时刻 0 开始活动巡游，且可以从任意一个他喜欢的城镇出发。

JOI 君可以在城镇 1 与城镇 2 之间双向移动。从一个城镇移动到另一个城镇所需的时间为：设 JOI 君在开始移动前已参加的活动数量为 $j$，则移动耗时为 $D + K \times j$。

给定活动与城镇之间移动的相关信息，请编写程序，求出 JOI 君最多能参加的活动数量。

输入格式

输入通过标准输入以如下格式给出：

$N$ $D$ $K$

$P_1$ $S_1$

$P_2$ $S_2$

$\vdots$

$P_N$ $S_N$

输出格式

在标准输出中，输出一行，表示 JOI 君最多能参加的活动数量。

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

4

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

6

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

8

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

11

提示

样例 1 解释

例如，JOI 君可以通过以下方式行动，参加 4 个活动：

1. 在时刻 0，JOI 君位于城镇 1。
2. 从时刻 1.1 到时刻 1.9，在城镇 1 参加活动 1。
3. 从时刻 2.1 到时刻 2.9，在城镇 1 参加活动 2。
4. 从时刻 3 到时刻 6，花费时间 $3 = D + K \times 2$，从城镇 1 移动到城镇 2。
5. 从时刻 6.1 到时刻 6.9，在城镇 2 参加活动 5。
6. 从时刻 7 到时刻 10，花费时间 $3 = D + K \times 3$，从城镇 2 移动到城镇 1。
7. 从时刻 10.1 到时刻 10.9，在城镇 1 参加活动 3。

无论采取何种行动，都无法参加 5 个或以上的活动，因此输出 4。

样例 2 解释

例如，JOI 君可以通过以下方式行动，参加 6 个活动：

1. 在时刻 0，JOI 君位于城镇 2。
2. 从时刻 2.1 到时刻 2.9，在城镇 2 参加活动 1。
3. 从时刻 3 到时刻 8，花费时间 $5 = D + K \times 1$，从城镇 2 移动到城镇 1。
4. 从时刻 8.1 到时刻 8.9，在城镇 1 参加活动 2。
5. 从时刻 11.1 到时刻 11.9，在城镇 1 参加活动 4。
6. 从时刻 12 到时刻 23，花费时间 $11 = D + K \times 3$，从城镇 1 移动到城镇 2。
7. 从时刻 23.1 到时刻 23.9，在城镇 2 参加活动 5。
8. 从时刻 24.1 到时刻 24.9，在城镇 2 参加活动 6。
9. 从时刻 25.1 到时刻 25.9，在城镇 2 参加活动 7。

无论采取何种行动，都无法参加 7 个或以上的活动，因此输出 6。

数据范围

• $1 \le N \le 200\,000$。
• $1 \le D \le 10^{12}$。
• $0 \le K \le 10^{12}$。
• $1 \le P_i \le 2$（$1 \le i \le N$）。
• $1 \le S_i \le 10^{12}$（$1 \le i \le N$）。
• $S_i \ne S_j$（$1 \le i < j \le N$）。
• 所有输入值均为整数。

子任务

1. （8 分）$K = 0$，$N \le 20$。
2. （11 分）$K = 0$，$N \le 4\,000$。
3. （24 分）$K = 0$。
4. （12 分）$N \le 160$。
5. （23 分）$N \le 4\,000$。
6. （22 分）无额外约束。

翻译由 Qwen3-235B 完成