AT_abc327_f [ABC327F] Apples

题目描述

在数轴上种有苹果树，有 $N$ 个苹果会从树上掉落。
具体来说，对于 $1\leq i\leq N$，在时刻 $T_i$，坐标 $X_i$ 处会有一个苹果掉落。

高桥君有一个耐久度为 $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$

输出格式

输出高桥君最多能获得的苹果数量。

输入输出样例 #1

输入 #1

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

输出 #1

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)$ 均不相同。
• 所有输入均为整数。

样例解释 1

高桥君选择 $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$ 个苹果可以被获得。无论如何操作，都无法获得 $6$ 个或更多的苹果，因此输出 $5$。

由 ChatGPT 4.1 翻译