RationalLee
Contest: Codeforces Round 652 (Div. 2)
Difficulty rating: 1400
Tags: greedy, math, sortings, two pointers

Lee just became Master in Codeforces, and so, he went out to buy some gifts for his friends. He bought $$$n$$$ integers, now it's time to distribute them between his friends rationally...

Lee has $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ in his backpack and he has $$$k$$$ friends. Lee would like to distribute all integers in his backpack between his friends, such that the $$$i$$$-th friend will get exactly $$$w_i$$$ integers and each integer will be handed over to exactly one friend.

Let's define the happiness of a friend as the sum of the maximum and the minimum integer he'll get.

Lee would like to make his friends as happy as possible, in other words, he'd like to maximize the sum of friends' happiness. Now he asks you to calculate the maximum sum of friends' happiness.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Next $$$3t$$$ lines contain test cases — one per three lines.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — the number of integers Lee has and the number of Lee's friends.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the integers Lee has.

The third line contains $$$k$$$ integers $$$w_1, w_2, \ldots, w_k$$$ ($$$1 \le w_i \le n$$$; $$$w_1 + w_2 + \ldots + w_k = n$$$) — the number of integers Lee wants to give to each friend.

It's guaranteed that the sum of $$$n$$$ over test cases is less than or equal to $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the maximum sum of happiness Lee can achieve.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Lee should give the greatest integer to the first friend (his happiness will be $$$17 + 17$$$) and remaining integers to the second friend (his happiness will be $$$13 + 1$$$).

In the second test case, Lee should give $$$\{10, 10, 11\}$$$ to the first friend and to the second friend, so the total happiness will be equal to $$$(11 + 10) + (11 + 10)$$$

In the third test case, Lee has four friends and four integers, it doesn't matter how he distributes the integers between his friends.

Example input:
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

Example output:
48
42
8000000000

Editorial:
$$$\mathcal Complete\; \mathcal Proof$$$ :
First if $$$w_i = 1$$$ for some $$$i$$$, then assign the greatest element to $$$i$$$-th friends, it's always better obviously.
Sort the elements in non-descending order and sort the friends in non-ascending order of $$$w_i$$$. Define $$$v_i$$$ the set of indices of elements to give to $$$i$$$-th friend. Also define $$$l_i$$$ the minimum element to give to $$$i$$$-th friend and $$$r_i$$$ the maximum element to give to $$$i$$$-th friend, and define $$$m = \max\limits_{1\,\le\,i\,\le\,k} w_i$$$.
Now it's easy to see that the first element of $$$a$$$(the smallest element) is always equal to $$$l_i$$$ for some $$$i$$$, Indeed it's better to have the rest of $$$v_i$$$ equal to a small number except one of them, which should be equal to a very large number. So we can greedily assign $$$a_1$$$, $$$a_2$$$ ... $$$a_{{w_i}-1}$$$ to $$$v_i$$$, and then assign $$$a_n$$$ to it, also it's better to have $$$w_i = m$$$. One can prove that there exist an optimal distributing such that the set($$$\{a_1, a_2 \ldots a_{m-1}, a_n\}$$$) is equal to one of $$$v_i$$$-s(proof is blow). So add $$$a_1 + a_n$$$ to the answer for remaining elements of $$$a$$$(excluding the set) and remaining friends(excluding one of the friends with maximum $$$w_i$$$) and so, it will be optimal.
Look at an optimal distributing (which maximizes sum of happiness), first element of $$$a$$$ is in $$$v_i$$$ for example, we want to prove that in at least one of the optimal distributings $$$w_i-1$$$ smallest elements of $$$a$$$ are in $$$v_i$$$ (including the first element), proof by contradiction:
If at least one of the smallest $$$w_i-1$$$ elements is not in $$$v_i$$$, then call the smallest of them $$$x$$$, lets say it's in $$$v_j$$$, now add $$$x$$$ to $$$v_i$$$(and erase it from $$$v_j$$$), instead add a greater number than $$$x$$$ in $$$v_i$$$ to $$$v_j$$$ (it's at least two of them, and one of them is $$$r_i$$$, so there exist another one, erase it from $$$v_i$$$ and add it to $$$v_j$$$), it's easy to see that sum of happiness won't decrease that way, continue the process until all $$$w_i-1$$$ smallest elements are in $$$v_i$$$, so we have an optimal answer which has all $$$w_i-1$$$ smallest elements in $$$v_i$$$, contradiction!
As we proved above, we have an optimal distributing such that all $$$w_i-1$$$ smallest elements are in $$$v_i$$$(for some $$$i$$$), now we want to prove that the greatest element is in $$$v_i$$$ in at least one of the optimal distributings, again proof by contradiction.
Lets say it's not that way, so look at an optimal distributing such that first $$$w_i-1$$$ elements are in $$$v_i$$$ and $$$r_i$$$ is not equal to the greatest element(for some $$$i$$$), if there exist such $$$j$$$ that $$$r_i < l_j$$$, then swap $$$r_i$$$ and $$$l_j$$$, the resulting distributing has the same happiness, continue it until no such $$$j$$$ exist, now lets say the greatest element of $$$a$$$ is in $$$v_j$$$ for some $$$j$$$, also we know that $$$r_j$$$ is equal to the greatest element of $$$a$$$ and $$$l_j \le r_i$$$(if $$$r_i < l_j$$$ then the process of swapping is not finished, which is contradiction). So now we can swap $$$r_i$$$ and $$$r_j$$$, again the resulting distributing has happiness greater than or equal to the happiness of the optimal distributing(the one we chose in the beginning), and so, its also an optimal distributing, and $$$r_i$$$ is equal to the greatest element, we have found an optimal distributing such that first $$$w_i-1$$$ elements of $$$a$$$ and $$$a_n$$$ are in $$$v_i$$$(for some $$$i$$$), contradiction!
Now we have proved that there exist an optimal distributing such that first $$$w_i-1$$$ elements of $$$a$$$ and $$$a_n$$$ are in $$$v_i$$$(for some $$$i$$$), call such optimal distributing STAR, and now the only remaining part is to prove that there exist an optimal distributing such that first $$$m-1$$$ elements of $$$a$$$ and $$$a_n$$$ are in $$$v_i$$$(for some $$$i$$$). See the whole algorithm, its like "we choose a permutation of friends then we do that greedy assignment to them one by one from left to right", now we want to prove that there exist an optimal distributing such that it's STAR and it's permutation is sorted in non-descending order of $$$w$$$, call them GOOD distributings. Again, proof by contradiction :
Choose a distributing such that it's a STAR, it's permutation(called $$$p$$$) is not sorted in non-descending order of $$$w$$$(otherwise it's a GOOD distributing, contradiction!), so there exist an $$$i$$$ such that $$$w_{p_i} > w_{p_{i+1}}$$$, now swap them(i. e. swap $$$p_i$$$ and $$$p_{i+1}$$$ and then do the same greedy assignment using the modified permutation of friends), it's easy to see that happiness of friends after $$$i+1$$$ in permutation $$$p$$$ wont change, also happiness of friends before $$$i$$$ in the permutation wont change as well.
Now look at the happiness of $$$p_i$$$ and $$$p_{i+1}$$$, you can realize that sum of happiness will increase.
You really don't need to prove it like that, it's not time friendly at all. ^-^