Mock Canadian Computing Competition: 2026 Stage 1, Junior #2

There are ~M~ players on a basketball team, and during a practice drill, each player shoots ~N~ free throws. Each player also has a certain number of free misses ~f[i]~.

The team will run ~L~ laps, where ~L~ represents the maximum penalty of a player. The penalty of a player is the number of shots they miss beyond their free misses. For example, if a player misses ~10~ shots but has ~6~ free misses, their penalty is ~10-6=4~. If that player misses ~6~ or fewer, their penalty is ~0~.

The team misses a total of ~T~ baskets, however it is unknown how many shots each player missed. Determine the minimum value of ~L~.

Constraints

~1 \leq M,N \leq 10^3~

~0 \leq T \leq M\times N~

~0 \leq f[i] \leq 10^3~

Input Specification

The first line contains ~N,M,T~

The next line contains ~M~ integers. The ~i^{th}~ integer represents ~f[i]~

Output Specification

Output the minimum number of laps the team must run.

Sample Input 1

6 4 21
4 1 2 1

Output for Sample Input 1

4

Explanation of Output for Sample Input 1

Consider the following distribution of missed shots, without the free misses: ~[6,5,6,4]~. Taking into account the free misses for each player ~[4,1,2,1]~, we get the following penalty distribution: ~[6-4,5-1,6-2,4-1]=[2,4,4,3]~. Thus, the number of laps the team must run is ~max(2,4,4,3)=4~. It can be shown that this is the minimum value of ~L~.

Sample Input 2

8 10 52
9 4 5 11 8 2 3 2 10 6

Output for Sample Input 2

0

Explanation of Output for Sample Input 2

All shots missed by the team can be covered by players' free misses collectively. One such distribution of missed shots is: ~[8,4,5,8,8,2,3,2,8,4]~. Thus, the minimum value of ~L~ is 0.

Sample Input 3

5 2 9
4 0

Output for Sample Input 3

4

Explanation of Output for Sample Input 3

~L=4~ can be obtained with the following distribution of missed shots: ~[5,4]~.