← 返回题目列表

Codeforces · 2143/B

B. 折扣

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

您想要购买价格为 $$$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$$$ 测试用例的答案 - 购买该测试用例中的所有产品所需的最低总成本。

示例

输入
复制

5
5 3
18 3 7 2 9
3 1 1
6 1
1 2 6 3 3 4
5
2 3
1 1
2 2 2
1 1
10
1
5 3
99 99 999 999 123
2 1 4

输出
复制

10
17
1
0
1197

注意

在第一个测试用例中,您可以对产品 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$$$ 硬币购买另一种。