P14332 [JOI2021 预选赛 R2] 活动巡游 / Event Hopping

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 君最多能参加的活动数量。

### 样例 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 完成