← 返回题目列表

Codeforces · 1369/C

C. 理性李

中文机器翻译题面 查看原题

Lee刚刚成为Codeforces的Master,所以他出去给朋友们买了一些礼物。他购买了 $$$n$$$ 整数,现在是时候在他的朋友之间理性分配了......

Lee 的背包里有 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$,并且他有 $$$k$$$ 个朋友。 Lee 希望将背包中的所有整数分配给他的朋友,这样第 $$$i$$$ 个朋友将恰好获得 $$$w_i$$$ 个整数,并且每个整数将被移交给恰好一个朋友。

让我们将朋友的幸福感定义为他将获得的最大和最小整数的总和。

李希望他的朋友尽可能快乐,换句话说,他希望朋友们的快乐总和最大化。现在他要求你计算朋友幸福感的最大总和。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

接下来的 $$$3t$$$ 行包含测试用例 - 每三行一个。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) - Lee 拥有的整数数量和 Lee 的朋友数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) - Lee 拥有的整数。

第三行包含 $$$k$$$ 整数 $$$w_1, w_2, \ldots, w_k$$$ ($$$1 \le w_i \le n$$$; $$$w_1 + w_2 + \ldots + w_k = n$$$) — Lee 想要给每个朋友的整数个数。

保证测试用例的 $$$n$$$ 总和小于或等于 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - Lee 可以获得的最大幸福感。

示例

输入 #1

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

输出 #1

48
42
8000000000

注意

在第一个测试用例中,Lee 应该将最大的整数给第一个朋友(他的幸福感将是 $$$17 + 17$$$),并将剩余的整数给第二个朋友(他的幸福度将是 $$$13 + 1$$$)。

在第二个测试用例中,Lee 应该给第一个朋友和第二个朋友 $$$\{10, 10, 11\}$$$,因此总幸福感将等于 $$$(11 + 10) + (11 + 10)$$$

在第三个测试用例中,Lee 有四个朋友和四个整数,无论他如何在朋友之间分配整数并不重要。