# Practice on Toph

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

# Playing With Stones

By tahsin_protik · Limits 10s, 512 MB

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

InputOutput
```3
3 2
1 2 3
3 2
1 4 10
5 4
2 8 5 5 10
```
```1
5
4
```

### Statistics

80% Solution Ratio

DibyaJyotiEarliest, 3w ago 