← 返回题目列表

Codeforces · 1662/L

L. 圣母德比

中文机器翻译题面 查看原题

米兰与国际米兰的德比即将进行,您被选为本场比赛的助理裁判,也称为边裁。您的任务是沿着边线(即球场一侧)移动,始终非常仔细地观察比赛,以检查是否有越位位置和其他违规行为。

足球在意大利是一件极其严肃的事情,因此尽可能长时间地密切关注球至关重要。这意味着您希望最大限度地增加您密切监控的踢腿次数。如果踢球发生时,您位于边线附近距离踢球发生地点最近的位置,那么您就可以密切监视踢球。

幸运的是,专家分析师已经能够准确预测比赛期间将发生的所有踢球。也就是说,给你两个整数列表,$$$t_1, \ldots, t_n$$$ 和 $$$a_1, \ldots, a_n$$$,表示比赛开始后 $$$t_i$$$ 秒将踢球,如果你位于边线 $$$a_i$$$ 位置,你可以密切监视这样的踢球。

游戏开始时,您从位置 $$$0$$$ 开始,沿着边线行走的最大速度为每秒 $$$v$$$ 单位(即,您每秒最多可以更改位置 $$$v$$$)。您可以密切监控的最大踢腿次数是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$v$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le v \le 10^6$$$) — 将进行的踢球次数和你的最大速度。

第二行包含 $$$n$$$ 整数 $$$t_1, \ldots, t_n$$$ ($$$1 \le t_i \le 10^9$$$) — 比赛中踢球的次数。时间序列保证严格递增,即 $$$t_1 < t_2 < \cdots < t_n$$$。

第三行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 沿着边线的位置,你必须在其中密切监视每次踢球。

输出

打印您可以密切监控的最大踢球次数。

示例

输入 #1

3 2
5 10 15
7 17 29

输出 #1

2

输入 #2

5 1
5 7 8 11 13
3 3 -2 -2 4

输出 #2

3

输入 #3

1 2
3
7

输出 #3

0

注意

在第一个示例中,可以在前 $$$3.5$$$ 秒内以最大速度向右移动,并停留在位置 $$$7$$$ 直到第一次踢球发生,然后立即以最大速度向右移动,以在位置 $$$17$$$ 观看第二次踢球。无法密切监视第二次踢球后的第三次踢球,因此最多可以看到 $$$2$$$ 踢球。