Apples

题目描述

有苹果树沿着数轴排成一行，且有 $N$ 个苹果从树上落下。
具体来说，对于每个 $1\leq i\leq N$，有一个苹果在时间 $T_i$ 于坐标 $X_i$ 落下。 Takahashi 有一个耐久度为 $D$ 且长度为 $W$ 的篮子，他可以恰好进行以下操作 一次。

选择正整数 $S$ 和 $L$。他在时间 $S-0.5$ 将篮子放置，使其覆盖区间 $L-0.5\leq x\leq L+W-0.5$，并在时间 $S+D-0.5$ 收回篮子。 他会获得在篮子放置到收回期间落入篮子覆盖范围内的所有苹果。

他在放置后不能移动篮子，也不能在收回后再次放置篮子。
求他最多能得到多少个苹果。

输入格式

输入从标准输入按以下格式给出： $N$ $D$ $W$ $T_1$ $X_1$ $T_2$ $X_2$ $\vdots$ $T_N$ $X_N$

输出格式

输出 Takahashi 能得到的最大苹果数量。

8 4 3
1 1
3 4
6 4
5 2
4 2
4 3
5 5
7 3

5

提示

$1 \leq N\leq 2\times 10^5$ $1 \leq D\leq 2\times 10^5$ $1 \leq W\leq 2\times 10^5$ $1 \leq T_i\leq 2\times 10^5$ $1 \leq X_i\leq 2\times 10^5$ 所有对 $(T_i,X_i)$ 都是不同的。 所有输入值均为整数。如果 Takahashi 选择 $S=3$ 和 $L=2$，他将在时间 $2.5$ 到 $6.5$ 之间将篮子放置在覆盖区间 $1.5\leq x\leq 4.5$。那么，他会得到以下五个苹果：

在时间 $T_2=3$ 于坐标 $X_2=4$ 落下的苹果 在时间 $T_3=6$ 于坐标 $X_3=4$ 落下的苹果 在时间 $T_4=5$ 于坐标 $X_4=2$ 落下的苹果 在时间 $T_5=4$ 于坐标 $X_5=2$ 落下的苹果 在时间 $T_6=4$ 于坐标 $X_6=3$ 落下的苹果

不存在方法能获得六个或更多的苹果，因此输出 $5$.

标签: AtCoder|abc327F

来源

AtCoder|abc327F