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.
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$
.
$1 \le T \le 11$
$1 \le N \le 10$
$0 \le M \le 10$
$0 \le a_i \le 10$
$1 \le T \le 11$
$1 \le N \le 500$
$0 \le M \le 500$
$0 \le a_i \le 500$
$1 \le T \le 11$
$1 \le N \le 10^5$
$0 \le M \le 10^9$
$0 \le a_i \le 10^9$
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$
.
Input | Output |
---|---|
3 3 2 1 2 3 3 2 1 4 10 5 4 2 8 5 5 10 | 1 5 4 |