该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

al7 因为偷懒被炒了，后在游戏中逃避现实的苦难。

al7 喜欢和零氪玩家比装备，和氪佬比操作，短暂地在服务器中叱咤风云。随后他被 超级玩家 2j(zoo8 以极致操作配上传说宝具一拳打爆。

题目描述

现在 al7 再一次碰上了 2j(zoo8，双方决定不再以装备和操作定胜负，而是各组建一支规模相当的军队进行对决。

军队比赛的方式很特殊。我们要求两支部队的人数均未n，采用n轮一对一的方式进行比赛。每轮具体为：两方各派上未上场过的一个士兵进行对决，能力值大的一方获胜。zj(zoo8 降下了仁慈，制定了三条对于 al7 有利的规则：

1.如果两个士兵能力值一样，则 al7 方的士兵获胜。

2.每轮总是 2j(zoo8 先派出士兵，al7 根据 zj(zoo8 派上场的士兵选择自己的士兵。

3.al7 事先知道 zj(zoo8 军队中每个士兵的能力值。

现在给出双方的军队信息，问 al7 最多可以胜利多少轮。

输入格式

第一行输出一个整数n，表示士兵的总数。

第二行输出一个整数$m_1$，表示 al7拥有军队的士兵组数，接着输出$m_1$个$a_i$和$b_i$表示拥有一组能力值为$a_i$的士兵，本组士兵数量一共有$b_i$个。

第三行输出一个整数$m_2$，表示 zj(zoo8 拥有军队的士兵组数，接着输出$m_2$个$a_i$和$b_i$表示拥有一组能力值为$a_i$的士兵，本组士兵数量一共有$b_i$个。

输出格式

唯一一行一个整数，表示答案。

数据范围

对于所有测试点：

$n\leq10^{18},m\leq{min(n,2*10^5)}$ 对于两方军队均满足，$1\leq{a_i}\leq{10^9};\sum{b_i}=n,\forall{b_i}>0$

任务点1，测试点编号1-2，满足$n\leq10$

任务点2，测试点编号3-8，满足$n\leq{10^3},\forall{b_i}=1$

任务点3，测试点编号9-12，满足$n\leq{10^5},\forall{b_i}=1$

任务点4，测试点编号13-20，无特殊限制

样例

6
3 1 2 1 2 4 2
3 5 2 1 2 4 2

4

时间空间限制

1000ms，524288K