Splitting Items
Contest: Educational Codeforces Round 169 (Rated for Div. 2)
Difficulty rating: 1100
Tags: games, greedy, sortings

Alice and Bob have $$$n$$$ items they'd like to split between them, so they decided to play a game. All items have a cost, and the $$$i$$$-th item costs $$$a_i$$$. Players move in turns starting from Alice.

In each turn, the player chooses one of the remaining items and takes it. The game goes on until no items are left.

Let's say that $$$A$$$ is the total cost of items taken by Alice and $$$B$$$ is the total cost of Bob's items. The resulting score of the game then will be equal to $$$A - B$$$.

Alice wants to maximize the score, while Bob wants to minimize it. Both Alice and Bob will play optimally.

But the game will take place tomorrow, so today Bob can modify the costs a little. He can increase the costs $$$a_i$$$ of several (possibly none or all) items by an integer value (possibly, by the same value or by different values for each item). However, the total increase must be less than or equal to $$$k$$$. Otherwise, Alice may suspect something. Note that Bob can't decrease costs, only increase.

What is the minimum possible score Bob can achieve?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases. Then $$$t$$$ cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le 10^9$$$) — the number of items and the maximum total increase Bob can make.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial costs of the items.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the minimum possible score $$$A - B$$$ after Bob increases the costs of several (possibly none or all) items.

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

Note:
In the first test case, Bob can increase $$$a_1$$$ by $$$5$$$, making costs equal to $$$[6, 10]$$$. Tomorrow, Alice will take $$$10$$$ and Bob will take $$$6$$$. The total score will be equal to $$$10 - 6 = 4$$$, and it's the minimum possible.

In the second test case, Bob can't change costs. So the score will be equal to $$$(15 + 10) - 12 = 13$$$, since Alice will take $$$15$$$, Bob will take $$$12$$$, and Alice — $$$10$$$.

In the third test case, Bob, for example, can increase $$$a_1$$$ by $$$1$$$, $$$a_2$$$ by $$$3$$$, and $$$a_3$$$ by $$$2$$$. The total change is equal to $$$1 + 3 + 2 \le 6$$$ and costs will be equal to $$$[4, 4, 4, 4]$$$. Obviously, the score will be equal to $$$(4 + 4) - (4 + 4) = 0$$$.

In the fourth test case, Bob can increase $$$a_1$$$ by $$$3$$$, making costs equal to $$$[9, 9]$$$. The score will be equal to $$$9 - 9 = 0$$$.

Example input:
4
2 5
1 10
3 0
10 15 12
4 6
3 1 2 4
2 4
6 9

Example output:
4
13
0
0

Editorial:
Let's sort the array in descending order and consider the first two moves of the game.
Since Alice goes first, she takes the maximum element in the array ($$$a_1$$$). Then, during his turn, Bob takes the second-largest element ($$$a_2$$$) to minimize the score difference.
Bob can increase his element in advance; however, he cannot make it larger than $$$a_1$$$ (since Alice always takes the maximum element in the array). This means that Bob needs to increase his element to $$$\min(a_1, a_2 + k)$$$. Then the game moves to a similar situation, but without the first two elements and with an updated value of $$$k$$$.
Thus, to solve the problem, we can sort the array and then iterate through it while maintaining several values. If the current index is odd (corresponding to Alice's turn), increase the answer by $$$a_i$$$. If the current index is even (corresponding to Bob's turn), increase the current value of $$$a_i$$$ by $$$\min(k, a_{i - 1} - a_i)$$$, decrease $$$k$$$ by that same value, and also subtract the new value of $$$a_i$$$ from the answer.