#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/E

Repovive

Stick Division - Repovive Standard Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

5E. Stick Division

2500 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 3sMemory: 512 MB

You are given $n$ sticks of integer lengths $a_1, a_2, \ldots, a_n$ .

You can perform at most $k$ cuts in total. In a single cut, you can choose a stick of integer length $L > 1$ and divide it into two sticks of integer lengths $x$ and $y$ such that $x > 0$ , $y > 0$ , and $x + y = L$ .

After performing at most $k$ cuts, your goal is to minimize the difference between the maximum and minimum lengths among all the resulting sticks.

Find the minimum possible difference between the length of the longest stick and the shortest stick.

Constraints

$1 \le t \le 100$
$1 \le n \le 10^5$
$1 \le a_i \le 10^5$
$0 \le k \le 10^9$
The sum of $n$ over all test cases is at most $10^5$ .

Input

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

3 1
3 4 5

Case 2

2 0
10 2

Case 3

4 100
5 5 5 5

Case 4

1 1
9

Case 5

3 2
7 8 9

Explanation

Case 1

We can make at most $1$ cut. If we don't make any cuts, the sticks are $\{3, 4, 5\}$ and the difference between the longest and shortest piece is $5 - 3 = 2$ . Even if we use our $1$ cut (for example, cutting the stick of length $5$ into $2$ and $3$ ), the new pieces would be $\{2, 3, 3, 4\}$ , resulting in a difference of $4 - 2 = 2$ . Thus, the minimum possible difference is $2$ .

Case 2

Since $k=0$ , no cuts are allowed. We simply calculate the difference between the longest and shortest initial sticks, which is $10 - 2 = 8$ .

Case 3

All sticks are already the same length (all are $5$ ). Without making any cuts, the difference between the longest and shortest piece is $5 - 5 = 0$ .

Case 4

There is only one stick. We don't even need to use our available cut; since there is only a single piece, both the longest and shortest pieces are the exact same stick, making the difference $9 - 9 = 0$ .

Case 5

The initial lengths are $\{7, 8, 9\}$ , giving an initial difference of $9 - 7 = 2$ . Even with $2$ available cuts, there is no way to divide the sticks such that the difference between the maximum and minimum resulting pieces becomes strictly less than $2$ . The minimum possible difference remains $2$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given $n$ sticks of integer lengths $a_1, a_2, \ldots, a_n$ .

After performing at most $k$ cuts, your goal is to minimize the difference between the maximum and minimum lengths among all the resulting sticks.

Find the minimum possible difference between the length of the longest stick and the shortest stick.

Constraints

$1 \le t \le 100$
$1 \le n \le 10^5$
$1 \le a_i \le 10^5$
$0 \le k \le 10^9$
The sum of $n$ over all test cases is at most $10^5$ .

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

Since $k=0$ , no cuts are allowed. We simply calculate the difference between the longest and shortest initial sticks, which is $10 - 2 = 8$ .

All sticks are already the same length (all are $5$ ). Without making any cuts, the difference between the longest and shortest piece is $5 - 5 = 0$ .