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

$ curl repovive.com/contests/17/problems/c

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

Nasser and Fady's MEX Game - Repovive Starter Round 5 | Repovive | Repovive

17C. Nasser and Fady's MEX Game

1500 pts2s256 MB

Nasser gives you an array $a$ of length $n$ consisting of positive integers.

Nasser and Fady will play a game consisting of exactly $k$ turns. Nasser takes the first turn. The game proceeds as follows:

On Nasser's turn: He chooses an index $i$ $(1 \le i \le n)$ such that $a[i] \ge 1$ , and decreases $a[i]$ by $1$ .
On Fady's turn: He chooses an index $i$ $(1 \le i \le n)$ and increases $a[i]$ by $1$ .

Nasser wants to maximize the MEX of the final array after all $k$ turns, while Fady wants to minimize it.

Both players play optimally. Your task is to help Nasser determine the maximum possible MEX value he can guarantee after $k$ turns.

The MEX (Minimum EXcluded) of an array is the smallest non-negative integer that does not appear in the array. For example:

$\text{MEX}([0, 1, 2, 4]) = 3$ --- since $0$ , $1$ , $2$ are present but $3$ is not.
$\text{MEX}([1, 2, 3]) = 0$ --- since $0$ is not present.
$\text{MEX}([0, 1, 3, 4]) = 2$ --- since $0$ , $1$ are present but $2$ is not.
$\text{MEX}([0, 0, 1]) = 2$ --- since $0$ , $1$ are present but $2$ is not.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \le t \le 10^4)$ - the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ $(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)$ - the length of the array and the number of turns.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$ - the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

Output

For each test case, output a single integer — the maximum MEX Nasser can guarantee.

Samples

Input

Case 1

1 1
1

Case 2

2 3
1 1

Case 3

3 5
1 2 3

Case 4

4 2
2 4 6 8

Case 5

5 1
1 3 5 7 9

Case 6

6 4
1 2 3 4 5 6

Explanation

Case 1

$n=1$ , $k=1$ , $a=[1]$ :

$k=1$ so there is only one turn and it is Nasser's turn.
Nasser decreases $a[1]$ from $1$ to $0$ .
Final array: $[0]$ .
$\text{MEX}([0]) = 1$ since $0$ is present but $1$ is not.
Answer: $1$ .

Case 2

$n=2$ , $k=3$ , $a=[1,1]$ :

$k=3$ so there are $3$ turns: Nasser, Fady, Nasser.
Turn $1$ (Nasser): Decreases $a[1]$ from $1$ to $0$ . Array: $[0, 1]$ .
Turn $2$ (Fady): Wants to minimize MEX. Increases $a[2]$ from $1$ to $2$ . Array: $[0, 2]$ .
Turn $3$ (Nasser): Decreases $a[2]$ from $2$ to $1$ . Array: $[0, 1]$ .
Final array: $[0, 1]$ .
$\text{MEX}([0, 1]) = 2$ since $0$ and $1$ are present but $2$ is not.
Answer: $2$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

Case 6

Nasser gives you an array $a$ of length $n$ consisting of positive integers.

Nasser and Fady will play a game consisting of exactly $k$ turns. Nasser takes the first turn. The game proceeds as follows:

On Nasser's turn: He chooses an index $i$ $(1 \le i \le n)$ such that $a[i] \ge 1$ , and decreases $a[i]$ by $1$ .
On Fady's turn: He chooses an index $i$ $(1 \le i \le n)$ and increases $a[i]$ by $1$ .

Nasser wants to maximize the MEX of the final array after all $k$ turns, while Fady wants to minimize it.

Both players play optimally. Your task is to help Nasser determine the maximum possible MEX value he can guarantee after $k$ turns.

The MEX (Minimum EXcluded) of an array is the smallest non-negative integer that does not appear in the array. For example:

$\text{MEX}([0, 1, 2, 4]) = 3$ --- since $0$ , $1$ , $2$ are present but $3$ is not.
$\text{MEX}([1, 2, 3]) = 0$ --- since $0$ is not present.
$\text{MEX}([0, 1, 3, 4]) = 2$ --- since $0$ , $1$ are present but $2$ is not.
$\text{MEX}([0, 0, 1]) = 2$ --- since $0$ , $1$ are present but $2$ is not.

Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \le t \le 10^4)$ - the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ $(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)$ - the length of the array and the number of turns.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$ - the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

$n=1$ , $k=1$ , $a=[1]$ :

$k=1$ so there is only one turn and it is Nasser's turn.
Nasser decreases $a[1]$ from $1$ to $0$ .
Final array: $[0]$ .
$\text{MEX}([0]) = 1$ since $0$ is present but $1$ is not.
Answer: $1$ .

$n=2$ , $k=3$ , $a=[1,1]$ :

$k=3$ so there are $3$ turns: Nasser, Fady, Nasser.
Turn $1$ (Nasser): Decreases $a[1]$ from $1$ to $0$ . Array: $[0, 1]$ .
Turn $2$ (Fady): Wants to minimize MEX. Increases $a[2]$ from $1$ to $2$ . Array: $[0, 2]$ .
Turn $3$ (Nasser): Decreases $a[2]$ from $2$ to $1$ . Array: $[0, 1]$ .
Final array: $[0, 1]$ .
$\text{MEX}([0, 1]) = 2$ since $0$ and $1$ are present but $2$ is not.
Answer: $2$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

17C. Nasser and Fady's MEX Game

Input

Output

Samples

17C. Nasser and Fady's MEX Game

Input

Output

Samples