# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 |

80% Solution Ratio

DibyaJyotiEarliest,

riyad000Fastest, 0.2s

riyad000Lightest, 918 kB

utsaroyShortest, 633B

Login to submit