您想要购买价格为 $$$a_1、a_2、\ldots、a_n$$$ 的 $$$n$$$ 产品。您可以:
- 单独购买产品 $$$i$$$,支付 $$$a_i$$$ 硬币,或者
- 使用折扣券作为团购的一部分购买。
您有 $$$k$$$ 折扣券,价值 $$$b_1、b_2、\ldots、b_k$$$。价值 $$$x$$$ 的代金券允许您准确选择 $$$x$$$ 产品,并仅支付 $$$x - 1$$$ 最贵的产品,因此,您可以认为该组中最便宜的产品是免费的。每个产品都可以包含在 最多 1 个 折扣团,即使不是免费的。此外,任何一张优惠券最多只能使用一次。
什么是 最低总成本 需要购买所有 $$$n$$$ 产品吗?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$) - 商品数量和可用折扣券数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 产品的价格。
第三行包含 $$$k$$$ 整数 $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le n$$$) — 折扣券的值。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,所有测试用例的 $$$k$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
打印 $$$t$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 测试用例的答案 - 购买该测试用例中的所有产品所需的最低总成本。
示例
输入复制
55 318 3 7 2 93 1 16 11 2 6 3 3 452 31 12 2 21 11015 399 99 999 999 1232 1 4
输出复制
1017101197
注意
在第一个测试用例中,您可以对产品 2、3 和 4 应用第一个折扣。您将支付两个最贵的产品(3 和 7 个硬币)并免费获得最便宜的一个,从而产生 $$$3 + 7 = 10$$$ 硬币的成本。然后,对产品 1 和 5 应用第二次和第三次折扣,免费获得这两种产品。总成本为 $$$10$$$ 硬币。
第二个测试用例中,您可以使用产品2、3、4、5、6的单次折扣。其中,最便宜的是产品2(需要2个金币),您可以免费获得。您支付剩余产品的费用:总共 $$$1 + 6 + 3 + 3 + 4 = 17$$$ 硬币。
在第三个测试用例中,仅提供一项折扣。您可以在这两种产品上使用它,免费获得更便宜的一种,并支付 $$$1$$$ 硬币购买另一种。