Nasser and Fady's MEX Game - Repovive Starter Round 5 | 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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

17C. Nasser and Fady's MEX Game

Input

Output

Samples

17C. Nasser and Fady's MEX Game

Input

Output

Samples