존(Farmer John) 아저씨가 농장에서 새로운 소 풀 뜯기 컨퍼런스를 개최합니다!

컨퍼런스에 참석해 풀을 뜯기 위해 전 세계의 소들이 지역 공항에 도착하고 있습니다. 구체적으로 총 N마리의 소가 공항에 도착하며, i번째 소는 ti 시간에 도착합니다.

존 아저씨는 공항에서 소들을 수송하기 위해 M대의 버스를 준비했습니다. 각 버스에는 최대 C마리의 소가 탑승할 수 있습니다.

존 아저씨는 공항에서 버스들을 대기시키며 도착하는 소들을 버스에 배정하려고 합니다.

버스는 해당 버스에 탑승하는 마지막 소가 도착하는 즉시 출발할 수 있습니다. 존 아저씨는 친절한 주인이 되고 싶기 때문에, 도착한 소들을 공항에서 너무 오래 기다리게 하고 싶지 않습니다.

존 아저씨가 버스를 최적으로 운행할 때, 도착한 소들이 기다려야 하는 '최대 대기 시간'의 최솟값은 얼마일까요?

소의 대기 시간은 해당 소의 공항 도착 시간과 소가 배정된 버스의 출발 시간 사이의 차이로 계산됩니다.

항상 모든 소를 태울 수 있음(M * C >= N)이 보장됩니다.

입력

첫째 줄에 소의 수 N, 버스의 수 M, 버스의 한계 용량 C가 공백으로 구분되어 주어집니다. (1 <= N, M <= 100,000, 1 <= C <= N)

둘째 줄에 각 소의 도착 시간을 나타내는 N개의 정수가 공백으로 구분되어 주어집니다. (0 <= ti <= 10^9)

출력

존 아저씨가 버스를 최적으로 배정했을 때, 소들이 기다려야 하는 최대 대기 시간의 최솟값을 한 줄에 출력합니다.

예제 입력 1

6 3 2
1 1 10 14 4 3

예제 출력 1

4

힌트

도착 시간이 [1, 1, 3, 4, 10, 14]인 소 6마리가 있습니다. 버스는 총 3대이며, 한 버스에 최대 2마리씩 탈 수 있습니다.

• 첫 번째 버스: 시간 1에 도착하는 소 2마리를 태우고 출발합니다. (대기 시간: 1 - 1 = 0)
• 두 번째 버스: 시간 3과 시간 4에 도착하는 소들을 태우고 시간 4에 출발합니다. (시간 3에 온 소가 1만큼 대기)
• 세 번째 버스: 시간 10과 시간 14에 도착하는 소들을 태우고 시간 14에 출발합니다. (시간 10에 온 소가 4만큼 대기)

이와 같이 배정하면 가장 오래 기다린 소의 대기 시간은 4가 되며, 이것이 가능한 최댓값의 최솟값입니다.

출처

USACO 2018 December Contest, Silver