E. 运送炸弹

远端评测题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：bomb.in 输出文件：bomb.out

小明参军后，很快被派往前线负责运送炸弹。他需要将 $n$ 枚炸弹送到 $k$ 个要塞，第 $i$ 个要塞需要运送 $w_i$ 枚炸弹。

每枚炸弹的攻击力由一个正整数表示，第 $i$ 枚炸弹的攻击力为 $a_i$。一个要塞得到的所有炸弹中，最大的攻击力与最小的攻击力之和为这个要塞的总体攻击力。请你帮小明合理分配这些炸弹到各个要塞，使得所有要塞的攻击力之和最大。

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 组询问，每组询问包含三行：

第一行为两个整数 $n$、$k$；

第二行为 $n$ 个正整数 $a_1$、$a_2$、……、$a_n$，$a_i$ 表示第 $i$ 枚炸弹的攻击力；

第三行为 $k$ 个正整数 $w_1$、$w_2$、……、$w_k$，$w_i$ 表示第 $i$ 个要塞需要运送 $w_i$ 枚炸弹。

输出包括 $t$ 行，第 $i$ 行为对第 $i$ 组询问的回答：

每行一个整数，表示这组询问中所有要塞的攻击力之和最大是多少。

3
4 2
1 7 13 17
1 3
6 2
10 10 10 10 11 11
3 3
4 4
1000000000 1000000000 1000000000 1000000000
1 1 1 1

48
42
8000000000

样例说明：

以第一组询问为例：为 $1$ 号要塞运送攻击力为 $17$ 的炸弹，该要塞的攻击力为 $17+17=34$ ；为 $2$ 号要塞运送攻击力为 $1$ 、 $7$ 、 $13$ 的炸弹，该要塞的攻击力为 $1+13=14$ ，总和为 $48$ 。

$1 \le t \le 10^4$

$1 \le k \le n \le 2\times 10^5$

$1 \le a_1 \le a_2 \le \cdots \le a_n \le 10^9$

$1 \le w_1 \le w_2 \le \cdots \le w_k \le n$

$w_1 + w_2 + \cdots + w_k = n$

题目保证所有询问中的 $n$ 之和不超过 $2 \times 10^5$。