Elfland Transport Committee

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

After a month of job-hunting (Santa fired him for sleeping on the job), Matthew the elf finally lands a job as a coordination officer for the Elfland Transport Committee! Before he can even celebrate this outstanding achievement, his boss gives him a major assignment to finish.

There are N snowmen that have come to Elfland for a gift-making conference. They need to take public transport to the conference, and need to board a sleigh T minutes after 9:00 am at latest in order to get there on time. Each snowman will arrive at the departure station t_i minutes after 9:00 am. The snowmen are expecting a sleigh to be waiting for them at the station the moment they get there.

The ETC only has M sleighs, each of which can wait at the station for at most C minutes before departing, taking all the snowmen that boarded it to the conference. Matthew's boss wants him to minimize C (since the ETC has not received their monthly budget yet), while still getting all the snowmen to their destination.

As Matthew's best friend, can you try to help him out?

Constraints

1 \le N, M \le 2 \times 10^5

1 \le t_i \le T \le 10^9

Input Specification

The first line will contain N and M and T.

The next line will contain N integers, t_1, t_2, ..., t_N.

Output Specification

Output C, the minimum amount of time each sleigh will wait.

Sample Input 1

10 3 100
1 3 5 7 9 30 55 70 86 90

Sample Output 1

25

Sample Explanation 1

The first sleigh, represented as an array, will hold snowmans: [1, 3, 5, 7, 9]

The second sleigh will hold: [30, 55]

The third sleigh will hold: [70, 86, 90]


Comments

There are no comments at the moment.