彩弹训练
时间限制：2秒
内存限制：256 MB
输入：标准输入
输出：标准输出
题目描述
在动物城警察局进行彩弹训练。场地上有 $h$ 行，从下到上编号为 $1$ 到 $h$，有 $n$ 个彩球飞行：第 $i$ 个彩球在时刻 $t_i$ 射出，沿行 $s_i$ 飞行，并在该秒内飞过该行。
博戈局长给了朱迪和尼克一个可移动护盾，高度为 $w$ 行。他们可以在某个时刻 $t_0$ 将其放置在最下面一行，此时在时刻 $t_0$，它将保护第 $1,2,\dots,w$ 行。护盾在一个位置停留一秒，然后立即向上移动一行。因此，护盾向上移动，直到它占据最上面的 $w$ 行，在那里停留一秒，然后消失。如果一个彩球在时刻 $t_i$ 时护盾已放置且 $s_i$ 属于此时护盾所占的行区间，则认为该彩球被阻挡。
求在最优选择 $t_0$ 下最多能阻挡多少个彩球。注意 $t_0$ 是正整数。
输入格式
第一行包含三个整数 $n$, $h$, $w$（$1 \le n \le 10^5$；$1 \le w \le h \le 10^9$）。
接下来 $n$ 行，每行一对整数 $t_i$ 和 $s_i$——第 $i$ 个彩球射出时间和所在行（$1 \le t_i \le 10^9$；$1 \le s_i \le h$）。
输出格式
输出一个整数——最多能阻挡的彩球数。
评分系统
| 子任务 | 分数 | 附加限制 | 所需子任务 |
|---|---|---|---|
| 1 | 5 | $n \le 300,\ h \le 30,\ t_i \le 200$ | 无 |
| 2 | 10 | $n \le 2000,\ t_i \le 500$ | 1 |
| 3 | 8 | $w = h$ | 无 |
| 4 | 12 | $w = 1$ | 无 |
| 5 | 15 | $n \le 2000$ | 1, 2 |
| 6 | 20 | $t_i \le 10^5$ | 1, 2 |
| 7 | 30 | 无 | 1–6 |
样例
样例 1
输入
4 5 2
1 1
1 2
2 2
3 4输出
4样例 2
输入
5 6 3
10 1
11 2
12 6
13 4
14 6输出
3注释
在第一个样例中，选择护盾放置时刻 $t_0=1$。护盾占用的行：
- 在时刻 $t=1$：$[1,2]$，阻挡彩球 $(1,1)$ 和 $(1,2)$；
- 在时刻 $t=2$：$[2,3]$，阻挡彩球 $(2,2)$；
- 在时刻 $t=3$：$[3,4]$，阻挡彩球 $(3,4)$。
在第二个样例中，选择护盾放置时刻 $t_0=10$。护盾占用的行：
- 在时刻 $t=10$：$[1,3]$，阻挡彩球 $(10,1)$；
- 在时刻 $t=11$：$[2,4]$，阻挡彩球 $(11,2)$；
- 在时刻 $t=12$：$[3,5]$，彩球 $(12,6)$ 未被阻挡；
- 在时刻 $t=13$：$[4,6]$，阻挡彩球 $(13,4)$。
- 之后护盾消失。