充电问题

题目描述

Carol 需要为 $n$ 辆电瓶车充电。第 $i$ 辆车的电池容量为 $a_i$ 瓦时。

充电站共有 $m$ 个充电插座。第 $j$ 个插座的功率为 $b_j$ 瓦。每个插座最多只能为一辆车充电，每辆车也只能通过一个插座充电。请计算在充电 $h$ 小时后，所有电瓶车所存储的最大总能量（以瓦时为单位）。

注意，当一辆电瓶车被某个插座完全充满后，该插座不能再为其他车充电。能量计算公式为功率乘以时间，例如，如果一个插座的功率是 $3$ 瓦，充电时间为 $3$ 小时，则电瓶车能够存储的能量为 $3 \times 3 = 9$ 瓦时。

输入格式

第一行一个整数 $T$ 表示数据组数。对于每组数据：

第一行三个整数 $n, m, h$。

第二行 $n$ 个整数 $a_{1\sim n}$ 表示每辆车的电池容量。

第三行 $m$ 个整数 $b_{1\sim m}$ 表示每个插座的功率。

输出格式

对于每组数据，输出一行一个整数，表示在 $h$ 小时后所有电瓶车所存储的最大总能量。

数据范围

• 对于 $30\%$ 的数据，$1 \leq \sum n, \sum m, h, a_i, b_i \leq 10$
• 对于 $60\%$ 的数据，$1 \leq \sum n, \sum m, h, a_i, b_i \leq 10^3$
• 对于 $100\%$ 的数据，$1 \leq T \leq 10^5$，$1 \leq \sum n, \sum m, h, a_i, b_i \leq 10^5$

样例

样例输入

3
1 2 2
100
20 40
2 1 2
10 20
11
3 2 1
30 30 30
40 20

样例输出

80
20
50

说明

在第一组数据中，使用第二个插座给唯一的车充电，$2$ 小时充了 $80$ 瓦时的电。