E-又双叒叕分糖果_第二十届西南科技大学ACM程序设计竞赛（同步赛）

又双叒叕分糖果

比赛主页

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题如其名， $\text{ChuTian}$ 对分糖果已经接近痴狂。这一次，他要做出新的糖果包，又双叒叕拉住了你来帮忙：

$\text{ChuTian}$ 有两个糖果包，这两个糖果包里分别有 $x,y$ 种不同重量的糖果，但是这两个糖果包里糖果的总数是相同的（都各有 $n$ 个糖果）。现在他又要为『世纪佳缘』里的群友制作一个特殊的糖果包。糖果包的制作要求如下：

$\text{ChuTian}$ 先丢弃掉两个糖果包里各一半的糖果数量。

$\text{ChuTian}$ 从两个糖果包里选择一些糖果制作成一个新的糖果包，但是新的糖果包里不能用相同重量的糖果。

$\text{ChuTian}$ 现在没有时间思考他能制作的新的糖果包里最多可以有多少个糖果，请你帮助他计算吧！

输入描述:

第一行输入一个正整数 $t$ $(1\le t \le 10^4)$ ，表示测试数据的组数。

每组测试数据：

第一行输入一个正整数 $n$ $(2\le n\le 10^5)$ ，表示两个糖果包里的糖果总数。保证 $n$ 为偶数。

第二行输入两个正整数 $x,y$ $(1\le x,y\le 10^5)$ ，分别表示第一个、第二个糖果包里不同重量糖果的种类数。

接下来 $x$ 行，每行输入两个正整数，第 $i$ 行两个正整数 $w_{1i},num_{1i}$ $(1\le w_{1i}\le10^9,1\le num_{1i}\le n)$ 表示重量为 $w_{1i}$ 的糖果有 $num_{1i}$ 个。保证 $\sum num_{1i} =n$ 并且 $w1$ 里面元素互不相同。

接下来 $y$ 行，每行输入两个正整数，第 $i$ 行两个正整数 $w_{2i},num_{2i}$ $(1\le w_{2i}\le10^9,1\le num_{2i}\le n)$ 表示重量为 $w_{2i}$ 的糖果有 $num_{2i}$ 个。保证 $\sum num_{2i} =n$ 并且 $w2$ 里面元素互不相同。

总共的： 保证 $\sum n \le 2\times 10^5$ 。

输出描述:

输出一行一个正整数表示答案。

示例1

输入

复制

输出

复制

备注:

对于样例 $1$ 的第一组测试数据：

通过计算，我们可以知道第一包糖果组成如下： ${1,1,4,5,1,4}$ ，而第二包糖果组成如下： ${1,9,1,9,8,10}$ 。

你可以这样教 $\text{ChuTian}$ ：从第一包糖果里丢弃掉重量为 $1$ 的糖果两个，重量为 $4$ 的糖果一个；从第二包糖果里丢弃掉重量为 $1$ 的糖果两个，重量为 $9$ 的糖果一个。

此时第一包糖果组成如下： ${5,1,4}$ ，而第二包糖果组成如下： ${9,8,10}$ 。

我们把里面所有糖果都选出来，组成一个新的糖果包。新的糖果包组成如下： ${1,4,5,8,9,10}$ 。所以新的糖果包有 $6$ 个糖果。

经过检验，新的糖果包里没有相同重量的糖果，且这种选法能使新的糖果包里的糖果个数最多。没有其他方法可以使这个数量更多了。