묶음 배달의 최소 반경

문제

배달 앱의 한 지역에는 일직선 도로가 있고, 이 도로 위 여러 지점에서 N건의 주문이 들어왔다. i번째 주문의 위치는 도로의 시작점에서 x_i 미터 떨어진 곳이며, 서로 같은 위치의 주문이 있을 수 있다. 이 주문들을 처리하기 위해 라이더를 최대 K명까지 투입할 수 있다. 각 라이더는 주문을 한 묶음으로 받아 배달하는데, 한 묶음에는 최대 M건의 주문만 담을 수 있다. 또한 한 묶음에 속한 주문들 중 가장 먼 위치와 가장 가까운 위치의 차이는 D 미터를 넘으면 안 된다. 모든 주문은 정확히 하나의 묶음에 속해야 하고, 사용하는 라이더 수는 K명 이하여야 하며, 묶음의 구성은 위치 순서와 무관하게 자유롭게 정할 수 있다. 이 조건을 만족하는 정수 D 중 가장 작은 값을 구하는 프로그램을 작성하라. 어떤 D를 잡아도 모든 주문을 처리할 수 없다면, 즉 주문 수가 너무 많아 K명이 M건씩 들어도 부족하다면 -1을 출력한다. 묶음 안의 주문이 한 건뿐이거나 위치가 모두 같다면 차이는 0이므로 D = 0이 답이 될 수 있다.

입력

첫 줄에 정수 N, K, M이 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 x_1 ... x_N이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200000, 1 ≤ K ≤ N, 1 ≤ M ≤ N, 0 ≤ x_i ≤ 10^9이며 x_i는 정렬되어 있지 않을 수 있다.

출력

조건을 만족하는 최소의 D를 한 줄에 출력한다. 불가능하면 -1을 출력한다.

5 2 3
1 9 4 2 8

3

4 1 3
5 5 5 5

-1

3 3 1
7 7 100

0

출처: Devin.KR 자체 제작