← 返回题目列表

Codeforces · 76/B

B. 小鼠

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

现代研究表明,一群饥饿的老鼠寻找一块奶酪的行为如下:如果有几块奶酪,那么每只老鼠都会选择最接近的一块。之后,所有老鼠都开始向所选的奶酪移动。当一只或多只老鼠到达目的地并且里面还有一块奶酪时,它们就会吃掉它并且吃得饱饱的。此后到达这一点的每只小鼠都保持饥饿。所有小鼠的移动速度相同。

如果有多种方法可以选择最接近的碎片,那么老鼠会以尽量减少饥饿老鼠数量的方式进行选择。为了验证这一理论,科学家们决定进行一项实验。他们将 N 只老鼠和 M 块奶酪放在笛卡尔平面上,所有老鼠都位于直线 y = Y0 上,所有奶酪块位于另一条直线 y = Y1 上。为了检查实验结果,科学家们需要一个程序来模拟一群饥饿的老鼠的行为。

编写一个程序来计算保持饥饿状态(即没有奶酪)的最小小鼠数量。

输入

输入的第一行包含四个整数 N (1 ≤ N ≤ 105)、M (0 ≤ M ≤ 105)、Y0 (0 ≤ Y0 ≤ 107)、Y1 (0 ≤ Y1 ≤ 107, Y0 ≠ Y1)。第二行包含严格递增的 N 个数字序列——小鼠的 x 坐标。第三行包含严格递增的 M 数字序列——奶酪的 x 坐标。所有坐标均为整数,绝对值不超过 107。

输出

输出的唯一一行应该包含一个数字——没有奶酪的老鼠的最小数量。

示例

输入 #1

3 2 0 2
0 1 3
2 5

输出 #1

1

注意

三只老鼠都会选择第一块奶酪。第二只和第三只老鼠会吃掉这块。第一个将保持饥饿状态,因为它正在朝同一块跑,但已经晚了。第二块奶酪将保持未吃状态。