Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Joe loves sleeping. He loves it so much that he’ll take naps whenever and wherever possible. He is currently on a car ride with his parents, which will be N minutes long. During the trip, there will be M events at distinct times t_1, t_2, \ldots, t_M that will wake Joe up if he is sleeping during those times. Joe plans to take up to K naps during these N minutes, and since he loves uniformity, he wants them all to be of the same length. Joe wishes to know the maximum number of minutes he can nap during the ride.


1 \leq N,K \leq 10^8

1 \leq M \leq \min(50\,000, N)

1 \leq t_i \leq N

Input Specification

The first line will contain three integers N, M and K.

The second line will contain M space separated integers, t_1, t_2, \ldots, t_M.

Output Specification

Output on a single line the maximum number of minutes Joe can sleep.

Sample input

22 2 5
6 17

Sample output



The best options is to take four 5-minute long naps during intervals [1,5], [7,11], [12,16], and [18,22].


There are no comments at the moment.