CF2143B Discounts

你打算购买 $n$ 个商品，价格分别为 $a_1, a_2, \ldots, a_n$。你可以选择以下两种方式购买每件商品： - 逐个购买商品 $i$，需支付 $a_i$ 个硬币； - 使用一张折扣券，将其作为团购的一部分购买。 你有 $k$ 张面值分别为 $b_1, b_2, \ldots, b_k$ 的折扣券。面值为 $x$ 的折扣券可以让你选中恰好 $x$ 个商品，并且只需支付其中价格最高的 $x - 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$ 个测试用例购买所有商品所需的最小总花费。

在第一个测试用例中，你可以把第一张折扣券用在第 2、3、4 号商品上，需支付价格最高的 2 件（3 和 7 个硬币），最便宜的那件免费，总共花费 $3 + 7 = 10$ 个硬币。然后用第 2、第 3 张折扣券买第 1、5 件商品，使它们都免费。总费用为 $10$。 在第二个测试用例中，可以用那张面值为 5 的折扣券，团购第 2、3、4、5、6 件商品，其中最便宜的是第 2 件（2 个硬币），免费。其余需支付 $1 + 6 + 3 + 3 + 4 = 17$ 个硬币。 在第三个测试用例中，只有一张折扣券，可以团购两件商品，免费最便宜的那一件，需支付 $1$ 个硬币。 由 ChatGPT 5 翻译