CodeChef : October Challenge 2017 – Max Mex

By | October 7, 2017

Max Mex

Source: CodeChef

Max Mex : You are given a multi-set S of N integers, and an integer K. You want to find the maximum value of minimal excluded non-negative integer (MEX) of the multi-set given that you are allowed to add at most any K integers to the multi-set. Find the maximum value of MEX that you can obtain.

Few examples of finding MEX of a multi-set are as follows. MEX of multi-set {0} is 1, {1} is 0, {0, 1, 3} is 2, {0, 1, 2, 3, 5, 6} is 4.

Input

The first line of the input contains an integer T denoting the number of testcases.

The first line of each test case contains two space seperated integers N and K denoting the size of the multi-set and the maximum number of extra integers that you can add in the multi-set respectively.

The second line contains N space separated integers denoting the multi-set SS1S2,…. SN.

Output

For each testcase, output the answer in a single line.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 105
  • 0 ≤ K ≤ 105
  • 0 ≤ Si ≤ 2 * 105

Subtasks

  • Subtask #1 (15 points): K=0.
  • Subtask #2 (85 points): Original Constraints.

Example

Input:
4
3 0
1 0 2
3 1
1 0 2
4 3
2 5 4 9
2 0
3 4

Output:
3
4
6
0

Explanation

Example case 1. As K = 0, so we can’t add any element to the multi-set. Elements of the set are {1, 0, 2}. The MEX value of this set is 3.

Example case 2. As K = 1, you are allowed to add at most 1 element to the multi-set. The multi-set are {1, 0, 2}. You can add element 3 to the multi-set, and it becomes {1, 0, 2, 3}. The MEX value of this multi-set is 4. There is no other way to have higher value of MEX of the set by adding at most one element to the multi-set.

Solution

Able to pass subtask 1. Working on the Solution to get subtask 2 also done.