← 返回题目列表

Codeforces · 1041/F

F. 管中的射线

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

给你一个内部反射的管子,表示为两条不重合但与 $$$Ox$$$ 线平行的管子。每条线都有一些特殊的整数点——传感器在管两侧的位置。

您将在管中发射激光射线。为此,您必须分别在第一行和第二行选择两个整数点 $$$A$$$ 和 $$$B$$$(坐标可以为负):点 $$$A$$$ 负责激光的位置,点 $$$B$$$ — 负责激光射线的方向。激光射线是从 $$$A$$$ 开始并指向 $$$B$$$ 的射线,它将从管的侧面反射(无论反射点是否有任何传感器)。仅当射线准确地击中传感器的位置时,传感器才会记录射线。

激光射线的示例。请注意,图像包含两个示例。 $$$3$$$ 传感器(由管侧的黑色粗体点表示)将记录蓝光,但只有 $$$2$$$ 会记录红色。

如果您分别在第一行和第二行选择点 $$$A$$$ 和 $$$B$$$,计算可以记录光线的最大传感器数量。

输入

第一行包含两个整数 $$$n$$$ 和 $$$y_1$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le y_1 \le 10^9$$$) — 第一行的传感器数量及其 $$$y$$$ 坐标。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 第一行传感器的 $$$x$$$ 坐标(按升序排列)。

第三行包含两个整数 $$$m$$$ 和 $$$y_2$$$ ($$$1 \le m \le 10^5$$$, $$$y_1 < y_2 \le 10^9$$$) — 第二行的传感器数量及其 $$$y$$$ 坐标。

第四行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \le b_i \le 10^9$$$) — 第二行传感器的 $$$x$$$ 坐标(按升序排列)。

输出

打印唯一的整数——可以记录光线的传感器的最大数量。

示例

输入 #1

3 1
1 5 6
1 3
3

输出 #1

3

注意

图像上由 $$$A_2$$$ 和 $$$B_2$$$ 对说明的解决方案之一。