Задача 8D. Автобусы ≡

Условие

Перевозка пассажиров происходит по следующему алгоритму: автобус приходит на вокзал и ожидает пассажиров, пока они не займут все M мест. Новый автобус приходит на вокзал каждые d минут, первый автобус приезжает в момент времени 0. Время ожидания пассажира  — это время, пока он стоит на остановке (если автобус стоит на остановке, а пассажир находится в нём, это не считается за ожидание).

Перевозчику пришли новые требования к перевозке пассажиров: теперь суммарное время ожидания для всех пассажиров не должно превышать T минут.

Вам точно известно количество пассажиров N, и для каждого из них момент времени t_i, когда пассажир приходит на вокзал. Перевозчик считает, что увеличение интервала между автобусами позволит уменьшить необходимое количество автобусов. Поэтому вам требуется выбрать максимально большой интервал между автобусами так, чтобы суммарное время ожидания для всех пассажиров не превышало T минут.

Формат входных данных

Первая строка входного файла содержит три целых числа N, M и T. Следующая строка содержит N целых чисел t_i. Гарантируется, что первый автобус не может забрать всех пассажиров.

Формат выходных данных

Выходной файл должен содержать одно целое число  — максимальный возможный интервал.

Ограничения

0 ≤ N, M ≤ 10⁶; 1 ≤ t_i ≤ 10⁶; 1 ≤ T ≤ 10⁹

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Примеры тестов

5 3 3
5 4 3 2 1

6

6 3 6
6 6 6 6 6 6

8