Playing With Stones

Kolu was playing with $N$ piles of stones. His target is to make all piles equal within $M$ moves, possibly zero.

In one move, he can choose two adjacent piles, i-th and j-th such that $|i - j|=1$. Then he can exchange at most $K$ stones among these two piles. He can make moves on the same two piles any number of times.

You will be given the total number of piles $N$, the number of stones in each pile, and the maximum number of moves allowed, $M$. He can choose a non-negative integer $K$ arbitrarily. Determine the minimum value of $K$ to make the number of stones in each pile equal within $M$ moves or report that it's impossible to do so.

Input

The first line contains the number of test case $T$.

In each test case, the first line contains two integer $N$ and $M$ - the number of piles Kolu has, the maximum number of moves he can make and the following line contains $N$ non-negetive integers, $a_1, a_2, \dots, a_N$, where $a_i$ means number of stones in i-th pile for all $1 \le i \le N$.

Constraints

Subtask 1 (up to 10 points)

$1 \le T \le 11$
$1 \le N \le 10$
$0 \le M \le 10$
$0 \le a_i \le 10$

Subtask 2 (up to 30 points)

$1 \le T \le 11$
$1 \le N \le 500$
$0 \le M \le 500$
$0 \le a_i \le 500$

Subtask 3 (up to 60 Points)

$1 \le T \le 11$
$1 \le N \le 10^5$
$0 \le M \le 10^9$
$0 \le a_i \le 10^9$

Output

If it's not possible to make all the piles equal within $M$ moves, print "$-1$" (without quotation). Otherwise, print the minimum value of $K$.

Sample

Input	Output
3 3 2 1 2 3 3 2 1 4 10 5 4 2 8 5 5 10	1 5 4