两家著名的竞争公司 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$$$。