На ферме Джона состоится съезд по поеданию травы.
Коровы со всего мира прибывают в местный аэропорт, чтобы посетить съезд
и поесть траву. А именно \(N\) (\(1 \leq N \leq 10^5\)) коров прибывают в
аэропорт, и корова \(i\) прибывает в момент времени \(t_i\) (\(0 \leq t_i \leq 10^9\)).
ФД организовал \(M\) (\(1 \leq M \leq 10^5\)) автобусов для транспортировки коров
из аэропорта. Каждый автобус может вместить до \(C\) (\(1 \leq C \leq N\)) коров.
ФД ждёт вместе с автобусами в аэропорту и собирается распределить прибывающих
коров по автобусам. Автобус убывает из аэропорта в момент, когда прибывает
последняя корова. ФД хочет, чтобы прибывающие коровы не ждали в аэропорту
слишком долго. Каково наименьшее значение максимального времени ожидания
из всех коров, если ФД оптимально назначит их по автобусам.
Время ожидания коровы есть разность между временем её прибытия и временем
отправления автобуса, в который она распределена.
Гарантируется, что \(MC \geq N\).
ФОРМАТ ВВОДА (файл convention.in):
Первая строка содержит три разделённых одиночными пробелами целых числа
\(N\), \(M\), \(C\). Следующая строка содержит \(N\) разделённых одиночными пробелами
целых чисел, представляющих время прибытия каждой коровы.
ФОРМАТ ВЫВОДА (файл convention.out):
Выведите одну строку, содержащую оптимальное минимальное максимальное время
ожидания для любой из прибывающих коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3 2
1 1 10 14 4 3
|
4
|