Horse Race

4

7 votes
Problem

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 ith 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 (1jM).
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(MN) 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

1T101N,M,X1051M,A[i]N

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?