题目背景

来源：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_n$ ，表示所有果干的妙值。

输出格式

输出到标准输出。

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

4
1
100
1
-2
1
-100
2
20 -10
3
1 -1 1
2
-1 1
5
2 3 3 -3 -3
5
6 6 6 -6 -6

0
20
3
26

提示

解释

为了方便起见，我们约定用 $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$		$11$
$4$			$10^9$	所有 $a_i,b_i$ 均为负数	$9$
$5$	$10^4$	$10^3$		无	$23$
$6$	$2\times 10^6$	$10^5$			$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)$ 也不会小于对应上界的一半。