{"problem":{"name":"B. Businessmen Problems","description":{"content":"Two famous competing companies _ChemForces_ and _TopChemist_ decided to show their sets of recently discovered chemical elements on an exhibition. However they know that no element should be present i","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF981B"},"statements":[{"statement_type":"Markdown","content":"Two famous competing companies _ChemForces_ and _TopChemist_ decided to show their sets of recently discovered chemical elements on an exhibition. However they know that no element should be present in the sets of both companies.\n\nIn order to avoid this representatives of both companies decided to make an agreement on the sets the companies should present. The sets should be chosen in the way that maximizes the total income of the companies.\n\nAll elements are enumerated with integers. The _ChemForces_ company has discovered $n$ distinct chemical elements with indices $a_1, a_2, \\ldots, a_n$, and will get an income of $x_i$ Berland rubles if the $i$\\-th element from this list is in the set of this company.\n\nThe _TopChemist_ company discovered $m$ distinct chemical elements with indices $b_1, b_2, \\ldots, b_m$, and it will get an income of $y_j$ Berland rubles for including the $j$\\-th element from this list to its set.\n\nIn other words, the first company can present any subset of elements from ${a_1, a_2, \\ldots, a_n}$ (possibly empty subset), the second company can present any subset of elements from ${b_1, b_2, \\ldots, b_m}$ (possibly empty subset). There shouldn't be equal elements in the subsets.\n\nHelp the representatives select the sets in such a way that no element is presented in both sets and the total income is the maximum possible.\n\n## Input\n\nThe first line contains a single integer $n$ ($1 \\leq n \\leq 10^5$) — the number of elements discovered by _ChemForces_.\n\nThe $i$\\-th of the next $n$ lines contains two integers $a_i$ and $x_i$ ($1 \\leq a_i \\leq 10^9$, $1 \\leq x_i \\leq 10^9$) — the index of the $i$\\-th element and the income of its usage on the exhibition. It is guaranteed that all $a_i$ are distinct.\n\nThe next line contains a single integer $m$ ($1 \\leq m \\leq 10^5$) — the number of chemicals invented by _TopChemist_.\n\nThe $j$\\-th of the next $m$ lines contains two integers $b_j$ and $y_j$, ($1 \\leq b_j \\leq 10^9$, $1 \\leq y_j \\leq 10^9$) — the index of the $j$\\-th element and the income of its usage on the exhibition. It is guaranteed that all $b_j$ are distinct.\n\n## Output\n\nPrint the maximum total income you can obtain by choosing the sets for both companies in such a way that no element is presented in both sets.\n\n[samples]\n\n## Note\n\nIn the first example _ChemForces_ can choose the set ($3, 7$), while _TopChemist_ can choose ($1, 2, 4$). This way the total income is $(10 + 2) + (4 + 4 + 4) = 24$.\n\nIn the second example _ChemForces_ can choose the only element $10^9$, while _TopChemist_ can choose ($14, 92, 35$). This way the total income is $(239) + (15 + 65 + 89) = 408$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"两家著名竞争公司 _ChemForces_ 和 _TopChemist_ 决定在展览上展示他们最近发现的化学元素集合。然而他们知道，任何元素都不应同时出现在两家公司的集合中。\n\n为了避免这种情况，两家公司的代表决定就各自公司应展示的集合达成协议。集合的选择应最大化两家公司的总收入。\n\n所有元素均用整数编号。_ChemForces_ 公司发现了 $n$ 个不同的化学元素，其索引为 $a_1, a_2, dots.h, a_n$，若第 $i$ 个元素出现在其集合中，则将获得 $x_i$ 伯兰卢布的收入。\n\n_TopChemist_ 公司发现了 $m$ 个不同的化学元素，其索引为 $b_1, b_2, dots.h, b_m$，若将第 $j$ 个元素包含在其集合中，则将获得 $y_j$ 伯兰卢布的收入。\n\n换句话说，第一家公司可以从 ${a_1, a_2, dots.h, a_n}$ 中选择任意子集（可能为空），第二家公司可以从 ${b_1, b_2, dots.h, b_m}$ 中选择任意子集（可能为空）。两个子集中不应包含相同的元素。\n\n请帮助代表们选择集合，使得没有任何元素同时出现在两个集合中，且总收入最大。\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）—— _ChemForces_ 发现的元素数量。\n\n接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $x_i$（$1 lt.eq a_i lt.eq 10^9$，$1 lt.eq x_i lt.eq 10^9$）——第 $i$ 个元素的索引及其在展览中使用所获得的收入。保证所有 $a_i$ 互不相同。\n\n下一行包含一个整数 $m$（$1 lt.eq m lt.eq 10^5$）—— _TopChemist_ 发明的化学元素数量。\n\n接下来的 $m$ 行中，第 $j$ 行包含两个整数 $b_j$ 和 $y_j$（$1 lt.eq b_j lt.eq 10^9$，$1 lt.eq y_j lt.eq 10^9$）——第 $j$ 个元素的索引及其在展览中使用所获得的收入。保证所有 $b_j$ 互不相同。\n\n请输出通过为两家公司选择集合（确保无元素同时出现在两个集合中）所能获得的最大总收入。\n\n在第一个例子中，_ChemForces_ 可选择集合 $(3, 7)$，而 _TopChemist_ 可选择 $(1, 2, 4)$。此时总收入为 $(10 + 2) + (4 + 4 + 4) = 24$。\n\n在第二个例子中，_ChemForces_ 可选择唯一元素 $10^9$，而 _TopChemist_ 可选择 $(14, 92, 35)$。此时总收入为 $(239) + (15 + 65 + 89) = 408$。\n\n## Input\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）—— _ChemForces_ 发现的元素数量。第 $i$ 行包含两个整数 $a_i$ 和 $x_i$（$1 lt.eq a_i lt.eq 10^9$，$1 lt.eq x_i lt.eq 10^9$）——第 $i$ 个元素的索引及其在展览中使用所获得的收入。保证所有 $a_i$ 互不相同。下一行包含一个整数 $m$（$1 lt.eq m lt.eq 10^5$）—— _TopChemist_ 发明的化学元素数量。第 $j$ 行包含两个整数 $b_j$ 和 $y_j$（$1 lt.eq b_j lt.eq 10^9$，$1 lt.eq y_j lt.eq 10^9$）——第 $j$ 个元素的索引及其在展览中使用所获得的收入。保证所有 $b_j$ 互不相同。\n\n## Output\n\n请输出通过为两家公司选择集合（确保无元素同时出现在两个集合中）所能获得的最大总收入。\n\n[samples]\n\n## Note\n\n在第一个例子中，_ChemForces_ 可选择集合 $(3, 7)$，而 _TopChemist_ 可选择 $(1, 2, 4)$。此时总收入为 $(10 + 2) + (4 + 4 + 4) = 24$。在第二个例子中，_ChemForces_ 可选择唯一元素 $10^9$，而 _TopChemist_ 可选择 $(14, 92, 35)$。此时总收入为 $(239) + (15 + 65 + 89) = 408$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ A = \\{ (a_i, x_i) \\mid i = 1, \\dots, n \\} $ be the set of element-index and income pairs for ChemForces.  \nLet $ B = \\{ (b_j, y_j) \\mid j = 1, \\dots, m \\} $ be the set of element-index and income pairs for TopChemist.\n\nDefine the universe of elements as $ U = \\{ a_1, \\dots, a_n \\} \\cup \\{ b_1, \\dots, b_m \\} $.  \nLet $ C = A \\cap B $ be the set of elements common to both companies (i.e., elements with same index in both lists).\n\nFor each element $ e \\in U $, define:\n- $ x(e) = $ income for ChemForces if $ e \\in A $, else 0.\n- $ y(e) = $ income for TopChemist if $ e \\in B $, else 0.\n\nThe constraint: For each $ e \\in U $, we may assign $ e $ to **at most one** company (ChemForces or TopChemist), or to neither, but **not both**.\n\nObjective: Maximize total income:\n$$\n\\sum_{e \\in U} \\left( \\text{if } e \\text{ assigned to ChemForces: } x(e), \\text{ else if assigned to TopChemist: } y(e), \\text{ else: } 0 \\right)\n$$\n\nThis is equivalent to:  \nFor each $ e \\in U $, choose one of three options:\n- Assign to ChemForces: gain $ x(e) $\n- Assign to TopChemist: gain $ y(e) $\n- Assign to neither: gain $ 0 $\n\nBut with the constraint that if $ e \\in A \\cap B $, then we must choose **exactly one** of $ x(e) $ or $ y(e) $, since both companies claim it and we cannot assign it to both.\n\n**Formal Optimization Problem:**\n\nLet $ S \\subseteq U $ be the set of elements assigned to ChemForces.  \nLet $ T \\subseteq U $ be the set of elements assigned to TopChemist.  \nConstraints: $ S \\cap T = \\emptyset $.\n\nMaximize:\n$$\n\\sum_{e \\in S} x(e) + \\sum_{e \\in T} y(e)\n$$\n\nSubject to:\n- $ S \\subseteq \\{ a_1, \\dots, a_n \\} $\n- $ T \\subseteq \\{ b_1, \\dots, b_m \\} $\n- $ S \\cap T = \\emptyset $\n\n**Equivalently, for each element $ e \\in U $:**\n- If $ e \\in A \\setminus B $: can only be assigned to ChemForces (gain $ x(e) $) or neither (0).\n- If $ e \\in B \\setminus A $: can only be assigned to TopChemist (gain $ y(e) $) or neither (0).\n- If $ e \\in A \\cap B $: must choose max($ x(e), y(e) $) or 0?  \n  But since $ x(e), y(e) > 0 $, we always choose the maximum of the two (never 0).\n\nThus, the optimal solution is:\n\nFor each $ e \\in U $:\n- If $ e \\in A \\setminus B $: include in $ S $ → gain $ x(e) $\n- If $ e \\in B \\setminus A $: include in $ T $ → gain $ y(e) $\n- If $ e \\in A \\cap B $: include in whichever company gives higher income → gain $ \\max(x(e), y(e)) $\n\nTherefore, the maximum total income is:\n$$\n\\sum_{\\substack{e \\in A \\setminus B}} x(e) + \\sum_{\\substack{e \\in B \\setminus A}} y(e) + \\sum_{\\substack{e \\in A \\cap B}} \\max(x(e), y(e))\n$$\n\n**Final Formal Statement:**\n\nLet $ A $ and $ B $ be multisets of (element, income) pairs for ChemForces and TopChemist respectively.\n\nDefine:\n- $ \\text{OnlyA} = \\{ e \\in A \\mid e \\notin B \\} $\n- $ \\text{OnlyB} = \\{ e \\in B \\mid e \\notin A \\} $\n- $ \\text{Both} = \\{ e \\in A \\cap B \\} $\n\nThen the maximum total income is:\n$$\n\\sum_{(e, x) \\in \\text{OnlyA}} x + \\sum_{(e, y) \\in \\text{OnlyB}} y + \\sum_{(e, x) \\in \\text{Both}} \\max\\left(x, y_e\\right)\n$$\nwhere $ y_e $ is the income of element $ e $ in TopChemist’s list.\n\nThis is computable in $ O(n + m) $ time via hashing or sorting.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF981B","tags":["sortings"],"sample_group":[["3\n1 2\n7 2\n3 10\n4\n1 4\n2 4\n3 4\n4 4","24"],["1\n1000000000 239\n3\n14 15\n92 65\n35 89","408"]],"created_at":"2026-03-03 11:00:39"}}