#B. 一拳打爆

    传统题 1000ms 512MiB

一拳打爆

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

题目背景

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,表示士兵的总数。

第二行输出一个整数m1m_1,表示 al7拥有军队的士兵组数,接着输出m1m_1aia_ibib_i表示拥有一组能力值为aia_i的士兵,本组士兵数量一共有bib_i个。

第三行输出一个整数m2m_2,表示 zj(zoo8 拥有军队的士兵组数,接着输出m2m_2aia_ibib_i表示拥有一组能力值为aia_i的士兵,本组士兵数量一共有bib_i个。

输出格式

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

数据范围

对于所有测试点:

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

任务点1,测试点编号1-2,满足n10n\leq10

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

任务点3,测试点编号9-12,满足n105,bi=1n\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

8.8模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-8-8 14:00
结束于
2024-8-8 17:30
持续时间
3.5 小时
主持人
参赛人数
27