На ферме Джона состоится съезд по поеданию травы.
Коровы со всего мира прибывают в местный аэропорт, чтобы посетить съезд и поесть траву. А именно n коров прибывают в аэропорт, и корова i прибывает в момент времени t[i]
(0 ≤ t[i]
≤ 10^9
). ФД организовал m автобусов для транспортировки коров из аэропорта. Каждый автобус может вместить до c коров. ФД ждёт вместе с автобусами в аэропорту и собирается распределить прибывающих коров по автобусам. Автобус убывает из аэропорта в момент, когда прибывает последняя корова. ФД хочет, чтобы прибывающие коровы не ждали в аэропорту слишком долго. Каково наименьшее значение максимального времени ожидания из всех коров, если ФД оптимально назначит их по автобусам. Время ожидания коровы есть разность между временем её прибытия и временем отправления автобуса, в который она распределена.
Гарантируется, что m * c ≥ n.
Первая строка содержит три целых числа n (1 ≤ n ≤ 10^5
), m (1 ≤ m ≤ 10^5
) , c (1 ≤ c ≤ n). Следующая строка содержит n разделённых одиночными пробелами целых чисел, представляющих время прибытия каждой коровы.
Выведите одну строку, содержащую оптимальное минимальное максимальное время ожидания для любой из прибывающих коров.
Если две коровы, прибывшие в момент 1 пойдут в первый автобус, а коровы прибывшие в моменты времени 3 и 4 - во второй, а коровы прибывшие в моменты времени 10 и 14 - в третий, то максимальное время ожидания будет 4 (корова, прибывшая в момент времени 10 будет ждать до времени 14).