seuOJ539 - The Greatest War

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：1000 ms
空间限制：1024 MiB
题目标签：Div.2, 2025

题目描述

你是一位国王，在你的手下有 $n$ 个士兵， $m$ 支矛和 $k$ 个盾。同时，每个士兵都有一个生命值 $a$ ，每支矛都有一个耐久度 $b$ ，每个盾都有一个防御值 $c$ 。

现在，你要带领着这群士兵和你的武器去击杀一条恶龙。战斗开始前，你可以给每一个士兵装备最多一支矛和一个盾，当然你也可以给一个士兵只装备一支矛或者只装备一个盾，或者什么都不装备。假如一些矛或一些盾没有被任何士兵装备，那么他们的耐久度和防御值会在战斗前会立刻变成 $0$ 。

在战斗时，每一秒中会发生如下事情：

首先，对于每一个还存活的士兵，如果其装备着一支耐久度大于 $0$ 的矛，那么该士兵会对恶龙造成 $1$ 点伤害，且矛的耐久度减少 $1$ 。
接下来，恶龙会对每一个还存活的士兵造成 $\frac{1}{x+y}$ 点伤害，减少每一个防御力大于 $0$ 的盾的 $\frac{1}{x+y}$ 防御力。其中 $x$ 为还存活的士兵数量， $y$ 为防御力大于 $0$ 的盾的数量。
接下来，假如一个士兵的生命值小于等于 $0$ ，该士兵会立刻死亡。如果某一个士兵死亡，那么其手中的矛的耐久度会立刻变成 $0$ ，其装备的盾的防御力也会立刻变成 $0$ 。

当没有士兵存活时，战斗就结束了。

假如以最优的方式给士兵装备矛和盾，那么恶龙受到的伤害最多是多少。

输入格式

第一行，一个整数 $t(1\le t\le 10^4)$ ，代表数据组数。

对于每组数据：

第一行，三个整数 $n,m,k(1\le n,m,k\le 2\cdot10^5)$ ，分别代表士兵的数量，矛的数量和盾的数量。

第二行， $n$ 个整数 $a_1,\dots,a_n(1\le a_i\le 10^9)$ ，代表每一个士兵的生命值。

第三行， $m$ 个整数 $b_1,\dots,b_m(1\le b_i\le 10^9)$ ，代表每一支矛的耐久度。

第四行， $k$ 个整数 $c_1,\dots,c_k(1\le c_i\le 10^9)$ ，代表每一个盾的防御值。

保证同一测试点内的 $n,m,k$ 的总和都不超过 $2\cdot10^5$ 。

输出格式

对于每组数据，输出一个整数，代表恶龙受到的伤害的最大值。

样例

输入样例

5
2 2 2
8 1
4 6
1 4
2 2 2
1 1
9 9
1 2
4 1 2
2 1 8 6
999999999
1 9
7 9 5
7 11 9 1 2 18 11
8 13 4 10 1 13 2 10 16
8 9 3 13 12
5 4 1
857487028 773029872 845119807 475685071 988386263
771098833 170131470 947400180 790206795
191652034

输出样例