{"raw_statement":[{"iden":"statement","content":"There are two small spaceship, surrounded by two groups of enemy larger spaceships. The space is a two-dimensional plane, and one group of the enemy spaceships is positioned in such a way that they all have integer $y$\\-coordinates, and their $x$\\-coordinate is equal to $-100$, while the second group is positioned in such a way that they all have integer $y$\\-coordinates, and their $x$\\-coordinate is equal to $100$.\n\nEach spaceship in both groups will simultaneously shoot two laser shots (infinite ray that destroys any spaceship it touches), one towards each of the small spaceships, all at the same time. The small spaceships will be able to avoid all the laser shots, and now want to position themselves at some locations with $x=0$ (with not necessarily integer $y$\\-coordinates), such that the rays shot at them would destroy as many of the enemy spaceships as possible. Find the largest numbers of spaceships that can be destroyed this way, assuming that the enemy spaceships can't avoid laser shots."},{"iden":"input","content":"The first line contains two integers $n$ and $m$ ($1 \\le n, m \\le 60$), the number of enemy spaceships with $x = -100$ and the number of enemy spaceships with $x = 100$, respectively.\n\nThe second line contains $n$ integers $y_{1,1}, y_{1,2}, \\ldots, y_{1,n}$ ($|y_{1,i}| \\le 10\\,000$) — the $y$\\-coordinates of the spaceships in the first group.\n\nThe third line contains $m$ integers $y_{2,1}, y_{2,2}, \\ldots, y_{2,m}$ ($|y_{2,i}| \\le 10\\,000$) — the $y$\\-coordinates of the spaceships in the second group.\n\nThe $y$ coordinates are not guaranteed to be unique, even within a group."},{"iden":"output","content":"Print a single integer – the largest number of enemy spaceships that can be destroyed."},{"iden":"examples","content":"Input\n\n3 9\n1 2 3\n1 2 3 7 8 9 11 12 13\n\nOutput\n\n9\n\nInput\n\n5 5\n1 2 3 4 5\n1 2 3 4 5\n\nOutput\n\n10"},{"iden":"note","content":"In the first example the first spaceship can be positioned at $(0, 2)$, and the second – at $(0, 7)$. This way all the enemy spaceships in the first group and $6$ out of $9$ spaceships in the second group will be destroyed.\n\nIn the second example the first spaceship can be positioned at $(0, 3)$, and the second can be positioned anywhere, it will be sufficient to destroy all the enemy spaceships."}],"translated_statement":[{"iden":"statement","content":"有两个小型宇宙飞船，被两组敌方大型宇宙飞船包围。空间是一个二维平面，其中一组敌方飞船的位置满足：它们的 $y$-坐标均为整数，且 $x$-坐标为 $-100$；另一组敌方飞船的位置满足：它们的 $y$-坐标均为整数，且 $x$-坐标为 $100$。\n\n每组中的每个敌方飞船将同时向两个小型飞船各发射一束激光（无限长的射线，触碰到任何飞船即摧毁之），所有激光同时发射。小型飞船能够避开所有激光，现在希望将它们定位在某两个 $x = 0$ 的位置（$y$-坐标不一定是整数），使得射向它们的激光能摧毁尽可能多的敌方飞船。求在敌方飞船无法躲避激光的前提下，最多能摧毁多少艘敌方飞船。\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 60$），分别表示 $x = -100$ 和 $x = 100$ 上的敌方飞船数量。\n\n第二行包含 $n$ 个整数 $y_{1,1}, y_{1,2}, dots.h, y_{1,n}$（$| y_{1,i} | lt.eq 10\\,000$）——第一组飞船的 $y$-坐标。\n\n第三行包含 $m$ 个整数 $y_{2,1}, y_{2,2}, dots.h, y_{2,m}$（$| y_{2,i} | lt.eq 10\\,000$）——第二组飞船的 $y$-坐标。\n\n$y$ 坐标在组内也可能重复。\n\n请输出一个整数——最多能摧毁的敌方飞船数量。\n\n在第一个例子中，第一个小型飞船可置于 $(0, 2)$，第二个置于 $(0, 7)$。这样，第一组的所有敌方飞船和第二组中的 $6$ 艘（共 $9$ 艘）将被摧毁。\n\n在第二个例子中，第一个小型飞船可置于 $(0, 3)$，第二个可置于任意位置，即可摧毁所有敌方飞船。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 60$），分别表示 $x = -100$ 和 $x = 100$ 上的敌方飞船数量。第二行包含 $n$ 个整数 $y_{1,1}, y_{1,2}, dots.h, y_{1,n}$（$| y_{1,i} | lt.eq 10\\,000$）——第一组飞船的 $y$-坐标。第三行包含 $m$ 个整数 $y_{2,1}, y_{2,2}, dots.h, y_{2,m}$（$| y_{2,i} | lt.eq 10\\,000$）——第二组飞船的 $y$-坐标。$y$ 坐标在组内也可能重复。"},{"iden":"output","content":"请输出一个整数——最多能摧毁的敌方飞船数量。"},{"iden":"examples","content":"输入\n3 9\n1 2 3\n1 2 3 7 8 9 11 12 13\n输出\n9\n\n输入\n5 5\n1 2 3 4 5\n1 2 3 4 5\n输出\n10"},{"iden":"note","content":"在第一个例子中，第一个小型飞船可置于 $(0, 2)$，第二个置于 $(0, 7)$。这样，第一组的所有敌方飞船和第二组中的 $6$ 艘（共 $9$ 艘）将被摧毁。在第二个例子中，第一个小型飞船可置于 $(0, 3)$，第二个可置于任意位置，即可摧毁所有敌方飞船。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ A = \\{a_1, a_2, \\dots, a_n\\} $ be the set of $ y $-coordinates of enemy spaceships at $ x = -100 $.  \nLet $ B = \\{b_1, b_2, \\dots, b_m\\} $ be the set of $ y $-coordinates of enemy spaceships at $ x = 100 $.\n\nLet $ p, q \\in \\mathbb{R} $ be the $ y $-coordinates of the two small spaceships positioned on the line $ x = 0 $.\n\nEach enemy spaceship at $ (-100, a_i) $ fires two laser rays: one toward $ (0, p) $ and one toward $ (0, q) $.  \nSimilarly, each enemy spaceship at $ (100, b_j) $ fires two laser rays: one toward $ (0, p) $ and one toward $ (0, q) $.\n\nA laser ray from $ (-100, a_i) $ to $ (0, p) $ is the line segment (or ray) connecting these two points.  \nThis ray will destroy **all** enemy spaceships lying on the same line.\n\nSimilarly for rays from $ (100, b_j) $ to $ (0, p) $ or $ (0, q) $.\n\n**Key Insight**:  \nA laser shot from $ (-100, a_i) $ to $ (0, p) $ passes through a point $ (100, b_j) $ **if and only if** the three points are colinear.\n\nThe slope from $ (-100, a_i) $ to $ (0, p) $ is $ \\frac{p - a_i}{100} $.  \nThe slope from $ (-100, a_i) $ to $ (100, b_j) $ is $ \\frac{b_j - a_i}{200} $.  \nFor colinearity with $ (0, p) $, we require:\n\n$$\n\\frac{p - a_i}{100} = \\frac{b_j - a_i}{200}\n\\quad \\Rightarrow \\quad\n2(p - a_i) = b_j - a_i\n\\quad \\Rightarrow \\quad\nb_j = 2p - a_i\n$$\n\nSimilarly, a ray from $ (100, b_j) $ to $ (0, p) $ passes through $ (-100, a_i) $ iff $ a_i = 2p - b_j $.\n\nThus, **for a fixed $ p $, the set of enemy ships destroyed by the ray from $ (0,p) $** is:\n\n- All $ a_i \\in A $ such that $ 2p - a_i \\in B $, **and**\n- All $ b_j \\in B $ such that $ 2p - b_j \\in A $\n\nIn other words, the ray from $ (0, p) $ destroys all enemy ships $ a_i \\in A $ and $ b_j \\in B $ such that $ a_i + b_j = 2p $.\n\nSimilarly, the ray from $ (0, q) $ destroys all $ a_i, b_j $ such that $ a_i + b_j = 2q $.\n\nEach enemy spaceship can be destroyed by **at most one** laser shot (since each fires two rays, but only one of them might hit another enemy, and we count destruction of enemies, not shots).\n\nBut note: each enemy spaceship is hit if **any** of the four laser rays (two from each small ship) passes through it.\n\nSo:  \nAn enemy at $ (-100, a_i) $ is destroyed if either:  \n- $ a_i + b_j = 2p $ for some $ b_j \\in B $, or  \n- $ a_i + b_j = 2q $ for some $ b_j \\in B $\n\nSimilarly, an enemy at $ (100, b_j) $ is destroyed if:  \n- $ a_i + b_j = 2p $ for some $ a_i \\in A $, or  \n- $ a_i + b_j = 2q $ for some $ a_i \\in A $\n\nTherefore, the total number of destroyed enemy ships is the number of distinct values in $ A \\cup B $ that appear in the set $ S = \\{ a_i + b_j \\mid a_i \\in A, b_j \\in B \\} $, **and** such that their sum equals $ 2p $ or $ 2q $.\n\nLet $ T = \\{ a_i + b_j \\mid a_i \\in A, b_j \\in B \\} $.  \nEach value $ s \\in T $ corresponds to a line (through $ (0, s/2) $) that destroys all enemy ships lying on that line: specifically, all $ a_i \\in A $ and $ b_j \\in B $ such that $ a_i + b_j = s $.\n\nBut note: for a fixed $ s $, the number of **enemy ships destroyed** by the line $ x=0, y = s/2 $ is:  \n- The number of $ a_i \\in A $ such that $ \\exists b_j \\in B $ with $ a_i + b_j = s $, **plus**  \n- The number of $ b_j \\in B $ such that $ \\exists a_i \\in A $ with $ a_i + b_j = s $\n\nBut since $ s = a_i + b_j $, for each pair $ (a_i, b_j) $ with sum $ s $, **both** $ a_i $ and $ b_j $ are destroyed.\n\nHowever, if multiple pairs yield the same $ s $, we must count **distinct** enemy ships, not pairs.\n\nSo for a fixed $ s \\in T $, define:\n\n- $ A_s = \\{ a_i \\in A \\mid \\exists b_j \\in B \\text{ s.t. } a_i + b_j = s \\} $\n- $ B_s = \\{ b_j \\in B \\mid \\exists a_i \\in A \\text{ s.t. } a_i + b_j = s \\} $\n\nThen the number of enemy ships destroyed by choosing $ p = s/2 $ is $ |A_s \\cup B_s| $?  \nWait — no: $ A_s \\subseteq A $, $ B_s \\subseteq B $, and $ A $ and $ B $ are disjoint sets (different x-coordinates), so $ A_s \\cap B_s = \\emptyset $.  \nThus, destroyed = $ |A_s| + |B_s| $.\n\nBut note: $ A_s $ is the set of $ a_i \\in A $ that participate in **at least one** pair summing to $ s $.  \nSimilarly for $ B_s $.\n\nSo for each $ s \\in T $, define:\n\n$$\nd(s) = |\\{ a_i \\in A : \\exists b_j \\in B, a_i + b_j = s \\}| + |\\{ b_j \\in B : \\exists a_i \\in A, a_i + b_j = s \\}|\n$$\n\nThen, if we choose two values $ s_1 = 2p $, $ s_2 = 2q $, the total number of destroyed enemy ships is:\n\n$$\nd(s_1) + d(s_2) - | \\text{enemy ships destroyed by both lines} |\n$$\n\nAn enemy ship might be destroyed by both lines if it lies on both lines — i.e., if $ a_i \\in A_{s_1} \\cap A_{s_2} $, or $ b_j \\in B_{s_1} \\cap B_{s_2} $.\n\nSo we must subtract the overlap.\n\nLet $ D = \\{ s \\in T \\} $, the set of all possible sums.\n\nWe want to choose two values $ s_1, s_2 \\in D $ (possibly $ s_1 = s_2 $) to maximize:\n\n$$\nd(s_1) + d(s_2) - \\left( |A_{s_1} \\cap A_{s_2}| + |B_{s_1} \\cap B_{s_2}| \\right)\n$$\n\nBut note: if $ s_1 = s_2 $, then we are choosing the same point, so the two small spaceships are at the same location — which is allowed? The problem says \"position themselves at some locations\" — plural, but doesn't forbid same location.\n\nBut if they are at the same location, then both shoot the same two rays? Actually, each small spaceship shoots two rays — one to each small spaceship. So if both small spaceships are at the same point $ (0,p) $, then each shoots one ray to the other — but that's the same ray. And each also shoots a ray to the other small spaceship — again, same ray. So effectively, only two rays are fired: both from each small ship to the common point. So we only get one line, not two.\n\nWait — re-read: \"Each spaceship in both groups will simultaneously shoot two laser shots (infinite ray that destroys any spaceship it touches), one towards each of the small spaceships\"\n\nSo each enemy ship shoots **two** rays: one to each small spaceship.\n\nSo if the two small spaceships are at the same point $ (0,p) $, then each enemy ship shoots **two rays**, but **both rays are identical** — same direction.\n\nSo the total set of rays is still just the set of rays from each enemy ship to $ (0,p) $ — so we get only one set of lines, not two.\n\nThus, if $ p = q $, then we only get one line, and the total destroyed is $ d(s) $ for $ s = 2p $.\n\nIf $ p \\ne q $, then we get two distinct lines, and we destroy the union of the ships on both lines.\n\nSo the problem reduces to:\n\n> Given sets $ A \\subseteq \\mathbb{Z} $, $ B \\subseteq \\mathbb{Z} $, and define for each $ s \\in \\mathbb{R} $:  \n> $ d(s) = |\\{ a \\in A : \\exists b \\in B, a + b = s \\}| + |\\{ b \\in B : \\exists a \\in A, a + b = s \\}| $  \n> Let $ T = \\{ a + b : a \\in A, b \\in B \\} $  \n> Find $ \\max_{s_1, s_2 \\in T} \\left[ d(s_1) + d(s_2) - |A_{s_1} \\cap A_{s_2}| - |B_{s_1} \\cap B_{s_2}| \\right] $\n\nBut note: since $ A $ and $ B $ are finite (size ≤ 60), and $ |T| \\leq 3600 $, we can iterate over all pairs $ (s_1, s_2) \\in T \\times T $.\n\nWe can precompute:\n\n- For each $ s \\in T $, compute:\n  - $ A_s = \\{ a \\in A : \\exists b \\in B, a + b = s \\} $\n  - $ B_s = \\{ b \\in B : \\exists a \\in A, a + b = s \\} $\n  - $ d(s) = |A_s| + |B_s| $\n\nThen for each pair $ (s_1, s_2) $, compute:\n\n$$\n\\text{total} = d(s_1) + d(s_2) - |A_{s_1} \\cap A_{s_2}| - |B_{s_1} \\cap B_{s_2}|\n$$\n\nAnd take the maximum.\n\nNote: $ A_{s_1} \\cap A_{s_2} $ is the set of $ a \\in A $ such that $ a + b_1 = s_1 $ and $ a + b_2 = s_2 $ for some $ b_1, b_2 \\in B $.  \nBut since $ s_1 \\ne s_2 $, for a fixed $ a $, $ a + b = s_1 $ and $ a + b = s_2 $ can't both hold unless $ s_1 = s_2 $.  \nSo $ A_{s_1} \\cap A_{s_2} $ is the set of $ a \\in A $ such that there exist $ b_1, b_2 \\in B $ with $ a + b_1 = s_1 $ and $ a + b_2 = s_2 $.  \nThat is, $ a $ appears in both $ A_{s_1} $ and $ A_{s_2} $, meaning $ a $ can form a sum $ s_1 $ with some $ b $, and $ s_2 $ with some (possibly different) $ b $.\n\nSame for $ B $.\n\nSo the overlap is just the number of $ a \\in A $ that are in both $ A_{s_1} $ and $ A_{s_2} $, and similarly for $ b \\in B $.\n\nWe can precompute for each $ a \\in A $, the set of $ s \\in T $ such that $ a + b = s $ for some $ b \\in B $.  \nSimilarly for each $ b \\in B $.\n\nThen for each pair $ (s_1, s_2) $, we can compute the intersection sizes by set operations.\n\nSince $ |T| \\leq 3600 $, and $ |A|, |B| \\leq 60 $, we can do $ O(|T|^2 \\cdot |A|) $, which is about $ 3600^2 \\cdot 60 \\approx 777.6 \\times 10^6 $ — borderline in C++ but in Python might be slow.\n\nBut note: $ |T| \\leq n \\cdot m \\leq 3600 $, but many sums may be repeated. Actually, the number of **distinct** sums is at most $ n \\cdot m = 3600 $, but we can reduce by using a set.\n\nBut 3600^2 = ~13 million pairs — which is acceptable in C++ or PyPy, and in Python if optimized.\n\nBut we can optimize: instead of iterating over all pairs of sums, we can iterate over all possible pairs of enemy ship positions? No, better to stick with sum values.\n\nAlternatively, we can note that the optimal solution will choose $ s_1, s_2 $ from the set of distinct sums that actually occur.\n\nLet $ S = \\text{set of distinct sums } a + b $ for $ a \\in A, b \\in B $.  \nLet $ |S| \\leq 3600 $.\n\nWe can precompute:\n\n- For each $ s \\in S $: $ A_s, B_s, d(s) $\n- For each $ a \\in A $, store $ \\text{sums}_A[a] = \\{ s \\in S : a + b = s \\text{ for some } b \\in B \\} $\n- For each $ b \\in B $, store $ \\text{sums}_B[b] = \\{ s \\in S : a + b = s \\text{ for some } a \\in A \\} $\n\nThen for each pair $ (s_1, s_2) \\in S \\times S $:\n\n- $ \\text{overlap}_A = \\sum_{a \\in A} \\mathbf{1}_{s_1 \\in \\text{sums}_A[a] \\text{ and } s_2 \\in \\text{sums}_A[a]} $\n- Similarly for $ \\text{overlap}_B $\n\nBut we can precompute for each $ a \\in A $, the set of sums it belongs to, then for each pair $ (s_1, s_2) $, we can compute:\n\n- $ \\text{overlap}_A = \\sum_{a \\in A} [s_1 \\in \\text{sums}_A[a] \\text{ and } s_2 \\in \\text{sums}_A[a]] $\n\nBut that’s $ O(|A| \\cdot |S|^2) \\approx 60 \\cdot 3600^2 \\approx 777.6 \\times 10^6 $, which is too slow in Python.\n\nBetter: precompute a matrix $ M_A[s_1][s_2] = $ number of $ a \\in A $ such that $ a \\in A_{s_1} \\cap A_{s_2} $\n\nWe can do:\n\nFor each $ a \\in A $, let $ \\text{sums}_A[a] $ be the set of sums involving $ a $.  \nThen for each pair $ (s_1, s_2) $, if $ s_1 \\in \\text{sums}_A[a] $ and $ s_2 \\in \\text{sums}_A[a] $, then increment $ M_A[s_1][s_2] $.\n\nWe can iterate over all $ a \\in A $, and for each $ a $, iterate over all pairs $ (s_1, s_2) $ in $ \\text{sums}_A[a] \\times \\text{sums}_A[a] $.\n\nThe number of sums per $ a $ is at most $ m \\leq 60 $, so per $ a $, we do $ 60^2 = 3600 $ operations.\n\nTotal for all $ a $: $ n \\cdot 3600 \\leq 60 \\cdot 3600 = 216000 $\n\nSame for $ B $: $ m \\cdot 3600 \\leq 216000 $\n\nSo total precomputation: ~432000 operations — very feasible.\n\nThen for each pair $ (s_1, s_2) \\in S \\times S $, we have:\n\n$$\n\\text{total}(s_1, s_2) = d(s_1) + d(s_2) - M_A[s_1][s_2] - M_B[s_1][s_2]\n$$\n\nAnd we take the maximum over all $ s_1, s_2 \\in S $.\n\nNote: $ s_1 $ and $ s_2 $ can be equal — then $ M_A[s_1][s_1] = |A_{s_1}| $, so:\n\n$$\n\\text{total}(s,s) = d(s) + d(s) - |A_s| - |B_s| = (|A_s| + |B_s|) + (|A_s| + |B_s|) - |A_s| - |B_s| = |A_s| + |B_s| = d(s)\n$$\n\nWhich is correct: if both small ships are at same point, we only get one line, destroying $ d(s) $ ships.\n\nSo this formula works for $ s_1 = s_2 $.\n\nThus, the algorithm:\n\n1. Read $ n, m $, arrays $ A $, $ B $\n2. Compute $ T = \\{ a + b \\mid a \\in A, b \\in B \\} $ → get set $ S $ of distinct sums\n3. For each $ s \\in S $:\n   - $ A_s = \\{ a \\in A : \\exists b \\in B, a + b = s \\} $\n   - $ B_s = \\{ b \\in B : \\exists a \\in A, a + b = s \\} $\n   - $ d(s) = |A_s| + |B_s| $\n4. For each $ a \\in A $, compute $ \\text{sums}_A[a] = \\{ s \\in S : \\exists b \\in B, a + b = s \\} $\n5. For each $ b \\in B $, compute $ \\text{sums}_B[b] = \\{ s \\in S : \\exists a \\in A, a + b = s \\} $\n6. Initialize 2D arrays $ M_A, M_B $ of size $ |S| \\times |S| $, indexed by sum values (use dict or map from sum to index)\n7. For each $ a \\in A $:\n   - Let $ L_a = \\text{sums}_A[a] $\n   - For each $ s_1 \\in L_a $, for each $ s_2 \\in L_a $: increment $ M_A[s_1][s_2] $\n8. Similarly for $ B $: for each $ b \\in B $, for each $ s_1, s_2 \\in \\text{sums}_B[b] $: increment $ M_B[s_1][s_2] $\n9. Initialize $ \\text{best} = 0 $\n10. For each $ s_1 \\in S $, for each $ s_2 \\in S $:\n    - $ \\text{score} = d(s_1) + d(s_2) - M_A[s_1][s_2] - M_B[s_1][s_2] $\n    - $ \\text{best} = \\max(\\text{best}, \\text{score}) $\n11. Print best\n\nNote: $ M_A[s_1][s_2] $ counts the number of $ a \\in A $ that are in both $ A_{s_1} $ and $ A_{s_2} $ — which is exactly $ |A_{s_1} \\cap A_{s_2}| $, same for $ B $.\n\nThis is correct.\n\nWe can use a dictionary mapping sum → index, or just use the sum value as key in a 2D dictionary.\n\nIn Python, we can use `defaultdict(int)` for `M_A` and `M_B`.\n\nLet’s code accordingly.\n\nBut note: the problem says \"Print a single integer – the largest number of enemy spaceships that can be destroyed.\"\n\nWe are done.\n\n**Final Formal Statement**:\n\nGiven finite sets $ A, B \\subseteq \\mathbb{Z} $, define:\n\n- $ T = \\{ a + b \\mid a \\in A, b \\in B \\} $\n- For each $ s \\in T $, define:\n  - $ A_s = \\{ a \\in A \\mid \\exists b \\in B, a + b = s \\} $\n  - $ B_s = \\{ b \\in B \\mid \\exists a \\in A, a + b = s \\} $\n  - $ d(s) = |A_s| + |B_s| $\n- Define $ M_A(s_1, s_2) = |\\{ a \\in A \\mid a \\in A_{s_1} \\cap A_{s_2} \\}| $\n- Define $ M_B(s_1, s_2) = |\\{ b \\in B \\mid b \\in B_{s_1} \\cap B_{s_2} \\}| $\n\nFind:\n$$\n\\max_{s_1, s_2 \\in T} \\left( d(s_1) + d(s_2) - M_A(s_1, s_2) - M_B(s_1, s_2) \\right)\n$$","simple_statement":null,"has_page_source":false}