지하철 임시 열차의 대기 한도

문제

지하철역의 임시 승강장에 N명의 승객이 도착한다. 운영자는 이 승객들을 모두 태우기 위해 임시 열차를 최대 K회 출발시킬 수 있다. 한 열차에는 최대 C명이 탈 수 있다. 임시 열차는 별도로 준비되어 있으므로 서로 다른 출발 사이에 필요한 최소 시간은 없으며, 여러 열차가 같은 시각에 출발해도 된다. 승객에게는 1번부터 N번까지 번호가 붙어 있다. 번호가 작을수록 도착 시각이 빠르거나 같으며, 도착 시각이 같은 승객 사이에서도 번호 순서를 유지한다. 승객을 배정할 때는 이 번호 순서를 지켜야 한다. 즉, 승객 전체를 번호가 연속한 비어 있지 않은 묶음들로 나누고, 각 묶음을 열차 한 대에 배정한다. 모든 승객은 정확히 한 묶음에 포함되어야 하며, 한 묶음의 승객 수는 C명 이하여야 한다. 각 열차는 자신에게 배정된 묶음의 마지막 승객이 도착하는 즉시 출발한다. 따라서 한 묶음의 첫 승객 번호가 l이고 마지막 승객 번호가 r이면 출발 시각은 r번 승객의 도착 시각이다. 그 묶음에 속한 승객의 대기 시간은 열차 출발 시각에서 자신의 도착 시각을 뺀 값이다. 도착과 동시에 출발하는 열차에 탄 승객의 대기 시간은 0이다. 운영자는 전체 승객 중 가장 오래 기다리는 승객의 대기 시간을 가능한 한 작게 만들려고 한다. 사용할 열차 수는 K대 이하면 되며 반드시 K대를 모두 사용할 필요는 없다. 모든 승객을 태울 수 있는 배정 중 최대 대기 시간이 가장 작은 값을 구해야 한다. 같은 최솟값을 만드는 배정이 여러 개라면 어느 배정을 선택해도 되며, 배정 자체는 출력하지 않는다. 열차 수와 정원 제한 때문에 모든 승객을 태울 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 승객 수 N, 사용할 수 있는 최대 열차 수 K, 열차 한 대의 정원 C가 공백으로 구분되어 주어진다. 모두 정수이며 1 ≤ N ≤ 40,000, 1 ≤ K ≤ N, 1 ≤ C ≤ N이다.
둘째 줄에 정수 t_1, t_2, …, t_N이 공백으로 구분되어 주어진다. t_i는 i번 승객의 도착 시각이며 0 ≤ t_1 ≤ t_2 ≤ … ≤ t_N ≤ 1,000,000이다. 시각의 단위는 초이다.

출력

모든 승객을 태울 수 있으면 전체 승객의 최대 대기 시간의 최솟값을 초 단위의 정수 하나로 출력한다. 모든 승객을 태울 수 없으면 -1을 출력한다.

6 3 3
0 2 3 8 9 15

3

5 2 2
1 1 4 8 8

-1

4 2 3
7 7 7 7

0

출처: Devin.KR 자체 제작