← 返回题目列表

Codeforces · 981/B

B. 商人问题

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

两家著名的竞争公司 ChemForces 和 TopChemist 决定在一次展览上展示他们最近发现的化学元素。然而他们知道两家公司的集合中不应出现任何元素。

为了避免这种情况,两家公司的代表决定就公司应展示的布景达成协议。应以最大化公司总收入的方式选择集合。

所有元素均用整数枚举。 ChemForces 公司发现了 $$$n$$$ 个不同的化学元素,索引为 $$$a_1、a_2、\ldots、a_n$$$,如果该列表中的第 $$$i$$$ 个元素位于该公司的集合中,则将获得 $$$x_i$$$ 伯兰卢布的收入。

TopChemist 公司发现了 $$$m$$$ 不同的化学元素,索引为 $$$b_1、b_2、\ldots、b_m$$$,并且它将获得 $$$y_j$$$ 伯兰卢布的收入,因为将此列表中的第 $$$j$$$ 个元素纳入其集合中。

换句话说,第一家公司可以呈现 $$$\{a_1, a_2, \ldots, a_n\}$$$ 中的任何元素子集(可能为空子集),第二家公司可以呈现 $$$\{b_1, b_2, \ldots, b_m\}$$$ 中的任何元素子集(可能为空子集)。子集中不应该有相等的元素。

帮助代表选择集合,使得两个集合中都没有出现任何元素,并且总收入是可能的最大值。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — ChemForces 发现的元素数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$x_i$$$ ($$$1 \leq a_i \leq 10^9$$$, $$$1 \leq x_i \leq 10^9$$$) — 第 $$$i$$$ 元素的索引以及其在展会上的使用收入。保证所有 $$$a_i$$$ 都是不同的。

下一行包含一个整数 $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — TopChemist 发明的化学品数量。

接下来的 $$$m$$$ 行的第 $$$j$$$ 包含两个整数 $$$b_j$$$ 和 $$$y_j$$$, ($$$1 \leq b_j \leq 10^9$$$, $$$1 \leq y_j \leq 10^9$$$)  — $$$j$$$-第一个元素及其在展览中的使用收入。保证所有 $$$b_j$$$ 都是不同的。

输出

打印通过为两家公司选择集合可以获得的最大总收入,并且两个集合中都不包含任何元素。

示例

输入 #1

3
1 2
7 2
3 10
4
1 4
2 4
3 4
4 4

输出 #1

24

输入 #2

1
1000000000 239
3
14 15
92 65
35 89

输出 #2

408

注意

在第一个示例中,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$$$。