You own a race course where \(N\) different races are played on a day and the performance of the winner is recorded in an array \(A\). The winner of the \(i'th\) race is \(A[i]\) horse. Being the owner, you are only interested in the performance of all the horses numbered from \(1\) to \(M\). Let's denote the number of races won by the horses numbered from \(1\) to \(M\) by array \(B\), where \(B[j]\) denotes the number of races won by horse \(j\) (\(1 \leq j \leq M\)).
Let \(K\) denote the minimum value among all the elements of the array \(B\). You are allowed to perform the following operations at most \(X\) times (maybe 0).
- Choose index \(i\) (\(1 <= i <= N\)) change the value of \(A[i]\) i.e. the winner of race \(i\).
You are given an integer \(X\) denoting the maximum number of operations you can perform. Find the maximum possible value of \(K\) after performing atmost \(X\) operations.
Note: There can be horses greater than \(M (M \leq N)\) participating in the race, but we only care about the horses numbered from \(1\) to \(M\).
Input Format
- The first line contains an integer \(T\), which denotes the number of test cases.
- The first line of each test case contains three integers, denoting the value of \(N\), \(M\), and \(X\) respectively.
- The second line of each test case contains \(N\) space-separated integers, denoting the elements of array \(A\).
Output Format
For each test case, print the maximum possible value of \(K\).
Constraints
\(1 \leq T \leq 10 \\ 1 \leq N, M, X \leq 10^5 \\ 1 \leq M, A[i] \leq N\)
For test case \(1\): Initially, the array \(B\) is \([2,4]\). Now, we can perform at most two operations, so if we change \(A[2]\) to \(1\). The array \(B\) will be \([3,4]\) and the minimum of array \(B\) i.e. \(K=3\). There is no way to increase the value of \(K\) by further operations. So, the answer will be \(3\).
For test case \(2\): Here initially, the array \(B\) is \([2,0,1]\) and we can perform at most \(1\) operations on the array \(A\). So if we change \(A[4]=2\). The array \(B\) will be \([2,1,1]\) and the minimum of array \(B\) i.e. \(K=1\). So, the answer will be \(1\).
For test case \(3\): Here initially, the array \(B\) is \([1,2]\) and we can perform at most \(2\) operations on the array \(A\). So if we change \(A[4]=1\). The array \(B\) will be \([2,2]\) and the minimum of array \(B\) i.e. \(K=2\). There is no way to increase the value of \(K\) by further operations. So, the answer will be \(2\).
