Greedy Monocarp
Contest: Educational Codeforces Round 172 (Rated for Div. 2)
Difficulty rating: 800
Tags: greedy, sortings

There are $$$n$$$ chests; the $$$i$$$-th chest initially contains $$$a_i$$$ coins. For each chest, you can choose any non-negative ($$$0$$$ or greater) number of coins to add to that chest, with one constraint: the total number of coins in all chests must become at least $$$k$$$.

After you've finished adding coins to the chests, greedy Monocarp comes, who wants the coins. He will take the chests one by one, and since he is greedy, he will always choose the chest with the maximum number of coins. Monocarp will stop as soon as the total number of coins in chests he takes is at least $$$k$$$.

You want Monocarp to take as few coins as possible, so you have to add coins to the chests in such a way that, when Monocarp stops taking chests, he will have exactly $$$k$$$ coins. Calculate the minimum number of coins you have to add.

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

Each test case consists of two lines:

- the first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 50$$$; $$$1 \le k \le 10^7$$$);
- the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$).

Output format:
For each test case, print one integer — the minimum number of coins you have to add so that, when Monocarp stops taking the chests, he has exactly $$$k$$$ coins. It can be shown that under the constraints of the problem, it is always possible.

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

Note:
In the first test case of the example, you don't have to add any coins. When Monocarp arrives, he will take the chest with $$$4$$$ coins, so he will have exactly $$$4$$$ coins.

In the second test case of the example, you can add $$$1$$$ coin to the $$$4$$$-th chest, so, when Monocarp arrives, he will take a chest with $$$4$$$ coins, then another chest with $$$4$$$ coins, and a chest with $$$2$$$ coins.

In the third test case of the example, you can add $$$3$$$ coins to the $$$1$$$-st chest and $$$5$$$ coins to the $$$2$$$-nd chest.

In the fourth test case of the example, you can add $$$1$$$ coin to the $$$1$$$-st chest and $$$1$$$ coin to the $$$3$$$-rd chest.

Example input:
4
5 4
4 1 2 3 2
5 10
4 1 2 3 2
2 10
1 1
3 8
3 3 3

Example output:
0
1
8
2

Editorial:
Consider several first chests that Monocarp will take before exceeding the limit if we don't add any coins; so, this will be the set of several largest chests such that the sum of this set is $$$s \le k$$$, but if the next chest is taken, the sum would exceed $$$k$$$.
For this set, the minimum number of coins that should be added is $$$k - s$$$. We can add exactly that amount if we increase the maximum element, the set of chests will include exactly the same elements, but now their sum is equal to $$$k$$$.
Now we have to consider the case where we add coins to some chest that is not the part of this set. Suppose Monocarp took some chest $$$i$$$, which initially had $$$a_i$$$ coins, but did not take chest $$$j$$$, such that $$$a_j > a_i$$$. In order for chest $$$i$$$ to be taken, its final value must be at least $$$a_j$$$, as Monocarp selects the maximum chest from the available ones. Let's suppose that $$$x$$$ coins were added to chest $$$i$$$, so that $$$a_i + x \ge a_j$$$. However, instead, we could have increased chest $$$j$$$ to the value $$$a_i + x$$$, and this would require fewer coins, since $$$a_j > a_i$$$. Thus, we have shown that it is not optimal to "change" the order of the chests, so we can always assume that Monocarp takes several chests that were the largest in the original order.