题目描述

给定一个 $n$ 行 $m$ 列的矩阵，矩阵初始所有元素均为 $0$。

给定两个正整数数组 $a=[a_1,a_2,...,a_x]$ 和 $b=[b_1,b_2,...,b_y]$，每个数组内部的元素严格递增。

你可以执行任意次操作，可以不执行操作。每次操作属于下面两种类型之一：

• 从数组 $a$ 选出一个数 $c$，再选择矩阵的某一行，将该行所有元素赋值为 $c$；
• 从数组 $b$ 选出一个数 $d$，再选择矩阵的某一列，将该列所有元素赋值为 $d$。

操作执行顺序任意，可以多次选择同一行、同一列或者同一个数值。

矩阵的代价定义为矩阵中至少出现一次的所有不同数的总和。求矩阵可以达到的最大代价。

输入

第一行输入一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

接下来是各组测试用例的描述。

每组测试用例第一行输入四个整数 \(n,m,x,y\)（$1 \le n,m \le 10^5$，$1 \le x,y \le n+m$），依次代表行数、列数、数组 $a$ 的长度、数组 $b$ 的长度。

每组测试用例第二行输入 $x$ 个整数 $a_1,a_2,...,a_x$（$1 \le a_1 \lt a_2 \lt ... \lt a_x\le n+m$）——数组 $a$ 的各个元素。

每组测试用例第三行输入 $y$ 个整数 $b_1,b_2,...,b_y$（$1 \le b_1 \lt b_2 \lt ... \lt b_y\le n+m$）——数组 $b$ 的各个元素。

输入附加约束：

• 所有测试用例的 $n$ 之和不超过 $10^5$；
• 所有测试用例的 $m$ 之和不超过 $10^5$。

输出

对每组测试用例输出一个整数，表示矩阵的最大可能代价。

样例

7
1 3 3 3
1 2 3
1 2 3
2 2 2 2
1 4
2 3
2 2 1 1
1
1
4 1 1 5
5
1 2 3 4 5
1 1 2 2
1 2
1 2
7 2 9 1
1 2 3 4 5 6 7 8 9
9
9 9 12 12
1 3 4 6 7 9 10 12 13 15 16 18
2 3 5 6 8 9 11 12 14 15 17 18

6
9
1
9
2
44
170

说明

第一组测试用例，可以先给仅有的那一行赋值 $3$，之后分别给第 $1$、第 $2$ 列赋值 $1$ 和 $2$。矩阵中存在 \(1,2,3\)，代价为 $6$。

第二组测试用例，可以先给两列分别赋值 $2$ 和 $3$，再给第 $1$ 行赋值 $4$。矩阵中存在 \(2,3,4\)，代价为 $9$。

原题链接

CF2253C