B. Businessmen Problems

两家著名竞争公司 _ChemForces_ 和 _TopChemist_ 决定在展览上展示他们最近发现的化学元素集合。然而他们知道，任何元素都不应同时出现在两家公司的集合中。 为了避免这种情况，两家公司的代表决定就各自公司应展示的集合达成协议。集合的选择应最大化两家公司的总收入。 所有元素均用整数编号。_ChemForces_ 公司发现了 $n$ 个不同的化学元素，其索引为 $a_1, a_2, dots.h, a_n$，若第 $i$ 个元素出现在其集合中，则将获得 $x_i$ 伯兰卢布的收入。 _TopChemist_ 公司发现了 $m$ 个不同的化学元素，其索引为 $b_1, b_2, dots.h, b_m$，若将第 $j$ 个元素包含在其集合中，则将获得 $y_j$ 伯兰卢布的收入。 换句话说，第一家公司可以从 ${a_1, a_2, dots.h, a_n}$ 中选择任意子集（可能为空），第二家公司可以从 ${b_1, b_2, dots.h, b_m}$ 中选择任意子集（可能为空）。两个子集中不应包含相同的元素。 请帮助代表们选择集合，使得没有任何元素同时出现在两个集合中，且总收入最大。 第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）—— _ChemForces_ 发现的元素数量。 接下来的 $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$ 互不相同。 下一行包含一个整数 $m$（$1 lt.eq m lt.eq 10^5$）—— _TopChemist_ 发明的化学元素数量。 接下来的 $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$ 互不相同。 请输出通过为两家公司选择集合（确保无元素同时出现在两个集合中）所能获得的最大总收入。 在第一个例子中，_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$。 ## Input 第一行包含一个整数 $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$ 互不相同。 ## Output 请输出通过为两家公司选择集合（确保无元素同时出现在两个集合中）所能获得的最大总收入。 [samples] ## Note 在第一个例子中，_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$。

Let $ A = \{ (a_i, x_i) \mid i = 1, \dots, n \} $ be the set of element-index and income pairs for ChemForces. Let $ B = \{ (b_j, y_j) \mid j = 1, \dots, m \} $ be the set of element-index and income pairs for TopChemist. Define the universe of elements as $ U = \{ a_1, \dots, a_n \} \cup \{ b_1, \dots, b_m \} $. Let $ C = A \cap B $ be the set of elements common to both companies (i.e., elements with same index in both lists). For each element $ e \in U $, define: - $ x(e) = $ income for ChemForces if $ e \in A $, else 0. - $ y(e) = $ income for TopChemist if $ e \in B $, else 0. The constraint: For each $ e \in U $, we may assign $ e $ to **at most one** company (ChemForces or TopChemist), or to neither, but **not both**. Objective: Maximize total income: $$ \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) $$ This is equivalent to: For each $ e \in U $, choose one of three options: - Assign to ChemForces: gain $ x(e) $ - Assign to TopChemist: gain $ y(e) $ - Assign to neither: gain $ 0 $ But 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. **Formal Optimization Problem:** Let $ S \subseteq U $ be the set of elements assigned to ChemForces. Let $ T \subseteq U $ be the set of elements assigned to TopChemist. Constraints: $ S \cap T = \emptyset $. Maximize: $$ \sum_{e \in S} x(e) + \sum_{e \in T} y(e) $$ Subject to: - $ S \subseteq \{ a_1, \dots, a_n \} $ - $ T \subseteq \{ b_1, \dots, b_m \} $ - $ S \cap T = \emptyset $ **Equivalently, for each element $ e \in U $:** - If $ e \in A \setminus B $: can only be assigned to ChemForces (gain $ x(e) $) or neither (0). - If $ e \in B \setminus A $: can only be assigned to TopChemist (gain $ y(e) $) or neither (0). - If $ e \in A \cap B $: must choose max($ x(e), y(e) $) or 0? But since $ x(e), y(e) > 0 $, we always choose the maximum of the two (never 0). Thus, the optimal solution is: For each $ e \in U $: - If $ e \in A \setminus B $: include in $ S $ → gain $ x(e) $ - If $ e \in B \setminus A $: include in $ T $ → gain $ y(e) $ - If $ e \in A \cap B $: include in whichever company gives higher income → gain $ \max(x(e), y(e)) $ Therefore, the maximum total income is: $$ \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)) $$ **Final Formal Statement:** Let $ A $ and $ B $ be multisets of (element, income) pairs for ChemForces and TopChemist respectively. Define: - $ \text{OnlyA} = \{ e \in A \mid e \notin B \} $ - $ \text{OnlyB} = \{ e \in B \mid e \notin A \} $ - $ \text{Both} = \{ e \in A \cap B \} $ Then the maximum total income is: $$ \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) $$ where $ y_e $ is the income of element $ e $ in TopChemist’s list. This is computable in $ O(n + m) $ time via hashing or sorting.