Discounts

We want to buy everything, so the total cost without discounts is fixed:

$$S = \sum_{i=1}^{n} a_i.$$

Every voucher makes exactly one product free: the cheapest product inside that voucher's chosen group. So the real job is:

maximize the total price of free products.

Then the answer is simply:

$$S - \text{freeSum}.$$

Key Observation

A voucher with value $x$ needs exactly $x$ products. Among those $x$, the cheapest one becomes free.

So if you want some product with price $v$ to be free using a voucher of size $x$, you must also put $x-1$ other products with price at least $v$ in that same group. Otherwise $v$ would not be the cheapest.

That means a voucher of size $1$ is insane value: it gives one product for free immediately. A voucher of size $2$ needs one extra product. A voucher of size $10$ needs nine extra products just to make one product free. Bigger vouchers are more expensive to “feed”.

So we should use smaller vouchers earlier, while expensive products are still available.

Greedy Strategy

Sort prices in decreasing order:

$$a_0 \ge a_1 \ge \dots \ge a_{n-1}.$$

Sort voucher sizes in increasing order:

$$b_0 \le b_1 \le \dots \le b_{k-1}.$$

Now process vouchers from smallest to largest.

For a voucher of size $x$, take the next $x$ most expensive unused products. Since they are sorted decreasingly, inside this block:

$$a_p, a_{p+1}, \dots, a_{p+x-1}$$

the cheapest one is $a_{p+x-1}$. That product becomes free, so we add it to freeSum, then move the pointer forward by $x$.

If fewer than $x$ products remain, we cannot use that voucher, so we skip it. No magic, no loophole, no “maybe group it weirdly” nonsense. It needs exactly $x$ products.

Why This Greedy Works

Take any voucher of size $x$. To make a product free, it must consume $x$ products total, and the free one is the cheapest among them.

For a fixed voucher size $x$, if we are deciding which unused products to spend, using the $x$ most expensive remaining products gives the highest possible free product for that voucher, because the free product is the minimum of the chosen group. The best minimum you can get from any $x$ unused products is the $x$-th most expensive unused product.

Now compare voucher sizes. Smaller vouchers consume fewer products per free item, so they should get priority on the expensive products. If a larger voucher is used before a smaller voucher, the larger voucher burns more expensive products just to create one free item. Swapping their order cannot make things worse: the smaller voucher can claim an expensive free item with fewer consumed products, leaving at least as much room for later vouchers.

So the optimal order is increasing $b_i$, and each voucher takes the next block of most expensive unused products.

Algorithm

1. Read $n$, $k$.
2. Read prices $a$ and compute their sum.
3. Sort $a$ in decreasing order.
4. Sort voucher sizes $b$ in increasing order.
5. Set ptr = 0 and freeSum = 0.
6. For each voucher size x:
   • if ptr + x <= n, then a[ptr + x - 1] becomes free;
   • add it to freeSum;
   • set ptr += x.
7. Print sum - freeSum.

Complexity

Sorting dominates:

$$O(n \log n + k \log k)$$

per test case, with total $n$ and $k$ bounded by $2 \cdot 10^5$, so this easily fits. Like, aggressively fits.