P11148 [THUWC 2018] 零食

来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](https://www.gitlink.org.cn/thusaa/thuwc2018)。 2018 清华大学信息学冬季体验营（THUWC 2018）D1T1。$\texttt{1s,1G}$。

Yazid 是一名清华大学的学生，他非常喜欢吃零食。 Yazid 共有 $n$ 包**薯片**，（由于它们的口味各不相同）Yazid 把他们从 $1$ 至 $n$ 编号；Yazid 还有 $m$ 包**果干**，Yazid 也把他们从 $1$ 至 $m$ 编号。 为了不引起歧义，我们规定：两包零食**类型**相同当且仅当它们同为薯片或果干。 Yazid 打算按一定顺序吃掉所有的零食。在开始吃一包零食后，直到这包零食被吃完前， Yazid 都不会吃其他零食。也就是说， Yazid 的吃零食顺序可以用一个**待吃零食的排列**来表示。 连续吃同一种食物可能会有别样的体验，所以，每包零食都有一个**妙值**。编号为 $i$（$1\leq i\leq n$）的薯片的妙值为 $a_i$，编号为 $i$（$1\leq i\leq m$）的果干的妙值为 $b_i$。 我们保证所有零食的妙值是整数，但需要注意的是，它们有可能为负。 在吃每包零食时，如果 Yazid 在其之前吃的零食与其类型相同，则 Yazid 会增加当前零食妙值的**快乐度**（吃第一包零食时不会获得快乐度）。初始时， Yazid 的快乐度为 $0$。 Yazid 希望获得最大的快乐度（需要提醒你的是，这个值可能是负的）。 饥肠辘辘的 Yazid 还要吃遍清华大学 $19$ 座食堂，所以请你帮他计算他能获得的最大快乐度。

从标准输入读入数据。 **本题包含多组数据**。输入的第一行为一个非负整数 $T$ ，表示数据组数。接下来依次描述每组数据，对于每组数据： 第一行 $1$ 个正整数 $n$ ，表示薯片的数量。 第二行 $n$ 个用空格隔开的整数 $a_1,\dots,a_n$，表示所有薯片的妙值。 第三行 $1$ 个正整数 $m$ ，表示果干的数量。 第四行 $m$ 个用空格隔开的整数 $b_1,\dots,b_m$，表示所有果干的妙值。

输出到标准输出。 对于每组数据，输出一行一个整数，表示 Yazid 能获得的最大快乐度。

#### 解释 为了方便起见，我们约定用 $A_i$ 表示编号为 $i$ 的薯片，用 $B_i$ 表示编号为 $i$ 的果干。 对于第 $1$ 组数据：无论以何种顺序吃这些零食， Yazid 都不会获得任何快乐度，因此答案为 $0$ 。 对于第 $2$ 组数据：最优方案可以是 $B_2\rightarrow B_1\rightarrow A_1$ ，可以在吃 $B_1$ 时获得 $20$ 的快乐度。可以证明不存在更优的解。 对于第 $3$ 组数据：按 $B_1\rightarrow B_2\rightarrow A_2\rightarrow A_3\rightarrow A_1$ 的顺序吃零食即可获得 $3$ 的快乐度。可以证明不存在更优的解。 #### 子任务 | 测试点编号 | $\sum(n+m)\le $ | $n,m\le $ | $\vert a_i\vert ,\vert b_i\vert \le $ | 其他约束 | 分值 | | :--: | :--: | :--: | :--: | :--: | :--: | | $1$ | $300$ | $4$ | $1,000$ | 无 | $7$ | | $2$ | $2\times 10^6$ | $10^5$ | $1$ | 无 | $8$ | | $3$ | $2\times 10^6$ | $10^5$ | $2$ | 无 | $11$ | | $4$ | $2\times 10^6$ | $10^5$ | $10^9$ | 所有 $a_i,b_i$ 均为负数 | $9$ | | $5$ | $10^4$ | $10^3$ | $10^9$ | 无 | $23$ | | $6$ | $2\times 10^6$ | $10^5$ | $10^9$ | 无 | $42$ | 其中， $\sum (n+m)$ 表示该测试点中所有数据的 $n,m$ 之和。例如，样例1中的 $\sum (n+m)$ 即为 $1+1+1+2+3+2+5+5=20$ 。 对于所有测试点，保证 $T\leq 5,000$ ， $\sum (n+m)\leq 2\times {10}^{6}$。 对于每个测试点的所有数据，保证 $n,m\leq 100,000$ ，$1\leq \left|a_i \right|,\left|b_i \right|\leq 10^9$。 对于所有测试点，保证：所有数据中 $n,m$ 的最大值、所有数据中 $\left| a_i\right|,\left| b_i\right|$ 的最大值分别不会小于该测试点 $n,m$ 、 $\left|a_i \right|,\left|b_i \right|$ 上界的 $\frac{2}{3}$ ； $\sum (n+m)$ 也不会小于对应上界的**一半**。