D. Avoid Minimums
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a_1, a_2, a_3, \dots, a_n$$$. Your task is to make all elements of $$$a$$$ equal. In order to do it, you can perform the following operation at most $$$k$$$ times:

  • choose any index $$$i$$$ from $$$1$$$ to $$$n$$$ and increase $$$a_i$$$ by one.
You can choose any element of the array, but if the chosen $$$a_i$$$ is strictly greater than the current minimum of the array, you'll earn one coin.

What is the maximum number of coins you can earn among all possible ways to make the array equal?

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Next, $$$t$$$ cases follow (all cases are independent).

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 10^{12}$$$) — the size of array $$$a$$$ and the maximum number of operations you can perform.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array itself.

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

Output

For each test case, if it's impossible to make all elements equal, print $$$-1$$$. Otherwise, print the maximum number of coins you can earn while making all elements equal.

Example
Input
4
3 16
1 10 2
4 20
6 2 4 9
5 9
7 7 7 7 7
2 1000000000000
1000000000 1000000000
Output
-1
11
0
499999999999
Note

In the first test case, you need at least $$$17$$$ operations to make all elements equal (or to get the array $$$[10, 10, 10]$$$).

In the second test case, you can, for example, increase $$$a_3 = 4$$$ to $$$10$$$, then increase $$$a_1 = 6$$$ to $$$10$$$, after that increase $$$a_4 = 9$$$ to $$$10$$$ and, finally, $$$a_2 = 2$$$ to $$$10$$$. You'll perform $$$19$$$ operations and earn $$$(10 - 4) + (10 - 6) + (10 - 9) = 11$$$ coins in total, since increasing the $$$a_2$$$ from $$$2$$$ to $$$10$$$ won't give you any coins.

In the third test case, you can leave the array unchanged or make all elements equal to $$$8$$$ — both strategies will give you $$$0$$$ coins.