E. BTS Brightness
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Andrew is at a BTS concert, and he wants to light his glow sticks to dance with his friends. There are $$$n$$$ glow sticks, and initially every stick has brightness $$$0$$$.

During each second, Andrew chooses exactly one glow stick. The chosen stick's brightness increases by $$$1$$$, while every other stick's brightness decreases by $$$1$$$. All changes are clipped to the interval $$$[0,T]$$$: a value below $$$0$$$ becomes $$$0$$$, and a value above $$$T$$$ becomes $$$T$$$.

Andrew wants the final brightnesses of the glow sticks to be $$$a_1,a_2,\ldots,a_n$$$. Determine the minimum number of seconds required to reach this configuration, or report that it is impossible.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$T$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$1\le T\le 10^{9}$$$) — the number of glow sticks and the maximum brightness.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le T$$$) — the desired brightnesses.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print the minimum number of seconds required to obtain the desired brightnesses. If it is impossible, print $$$-1$$$.

Example
Input
4
2 3
2 2
1 7
5
4 100
0 0 1 2
3 1
0 0 1
Output
-1
5
4
1
Note

In the first test case, it can be proven that the requested configuration cannot be reached.

In the second test case, Andrew chooses the only glow stick $$$5$$$ times.

In the third test case, choosing sticks in the order $$$4,4,4,3$$$ produces the requested configuration.

In the fourth test case, Andrew only needs to choose the third stick once.