AT_joi2021_yo2_c イベント巡り (Event Hopping)

某地有两个镇。为简便，分别称其为 $1$ 镇和 $2$ 镇。 在一段时间内，这两个镇共举行了 $N$ 次活动。第 $i$ 次活动在 $P_i$ 镇举行，时间从 $(S_i+0,1)$ 持续到到 $(S_i+0.9)$。若想参与第 $i$ 次活动，需要在这段时间内在 $P_i$ 镇。 你从 $0$ 时刻开始在这两个城市之间移动。你可以选择你开始时所在的镇。在两个城镇之间移动所需的时间为 $(D+K\times j)$，其中 $j$ 是你之前所参加的活动数。 请求出你最多能参加多少次活动。

第一行输入三个整数 $N,D,K$。 随后输入 $N$ 行，第二行输入两个整数 $P_i$ 和 $S_i$。

一行一个整数，最多可参加的活动数。

样例解释请到 AtCoder 查看。 #### 数据规模与约定 对于 $100\%$ 的数据，满足： - $1\le N\le 200000$； - $1\le D,S_i\le 10^{12}$，当 $1\le i\lt j\le N$ 时 $S_i\neq S_j$； - $0\le K\le 10^{12}$； - $P_i\in \{1,2\}$； - 输入的所有值都为整数。 **本题有部分分。** 各子任务分值及特殊限制见下： - Subtask 0：为样例，$0$ 分。 - Subtask 1：$K=0$，$N\le 20$，$8$ 分。 - Subtask 2：$K=0$，$N\le 4000$，$11$ 分。 - Subtask 3：$K=0$，$24$ 分。 - Subtask 4：$N\le 160$，$12$ 分。 - Subtask 5：$N\le 4000$，$23$ 分。 - Subtask 6：无特殊限制，$22$ 分。