Triway Cup '19 Summer D - Napping

View as PDF

Submit solution

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

Authors:
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, \dots, 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.

Constraints

1 \le N,K \le 10^8

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

1 \le t_i \le 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, \dots, 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

20

Explanation

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


Comments

There are no comments at the moment.