Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача Е. Переподготовка

Задачу добавил: alef

Успешно сдано решений: 20

Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт

Стив пытался найти логику в действиях менеджеров Quantum Artificial Intelligence. Впрочем, тайное уже становилось явным. Компания Quantum Artificial Intelligence хотела стать единственным партнёром Smart Industrial Robots. Однако Smart Industrial Robots настаивала на том, что в компании-партнёре должно работать достаточное количество квалифицированных сотрудников. Если считать и сотрудников Quantum Artificial Intelligence, и сотрудников Gadget Operating System, необходимая численность набирается. А вот квалификацию требуется подтверждать экзаменом.

Для каждого сотрудника известно количество дней di, в течение которых он может подготовиться к экзамену, чтобы сдать его блестяще на следующий день после завершения подготовки. Но если знания не применяются на практике, они постепенно утрачиваются. Если сотрудник будет сдавать экзамен не на следующий день, а через день по завершении подготовки, то сдаст его на балл ниже; через два дня — на два балла ниже и т.д. Квалификация считается подтверждённой, если сотрудник сдал экзамен не хуже, чем на m баллов ниже идеальной оценки.

Менеджеры Quantum Artificial Intelligence хотят, чтобы все сотрудники немедленно приступили к подготовке к экзамену.

По техническим причинам одновременно сдавать экзамен могут не более k человек. Организация экзамена — достаточно хлопотное дело, и менеджеры хотели бы обойтись как можно меньшим количеством экзаменов.

Ваша задача — определить, какое минимальное количество экзаменов потребуется назначить, чтобы все сотрудники подтвердили свою квалификацию.

Входные данные

В первой строке содержатся целые числа n, m, k (1 ≤ n,  k ≤ 105, 0 ≤ m ≤ 109) — количество сотрудников, допустимое отклонение от полного балла, максимально возможное количество одновременно экзаменующихся соответственно.

Во второй строке содержится n целых чисел d1, d2, ..., dn, где di (1 ≤ di ≤ 109) — количество дней, которое требуется сотруднику #i, чтобы подготовиться к экзамену.

Выходные данные

В первой строке выведите минимально возможное количество экзаменов, которое придётся назначить, чтобы все сотрудники подтвердили свою квалификацию.

Примеры

Входные данные
4 3 3
5 8 13 21
Выходные данные
3
Входные данные
10 5 3
1 6 4 15 4 10 8 2 12 5
Выходные данные
4

Сдать задачу

Задать вопрос жюри по этой задаче