Задача Е. Переподготовка
Задачу добавил: alef
Успешно сдано решений: 20
Стив пытался найти логику в действиях менеджеров 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