Сушка
Сушка
Очень трудно стирать и особенно сушить белье в зимний период. Но Джейн очень умная девочка. Она не боится этого скучного процесса. Для ускорения процесса сушки Джейн решила использовать радиатор. Однако радиатор мал, и способен выдержать в каждый момент времени только одну вещь.
Джейн хочет выполнить сушку в минимально возможное время. Она просит Вас написать программу, которая вычислит минимальное время сушки для данного набора одежды.
Джейн только что постирала n вещей. Во время стирки каждая из них набрала ai
единиц воды. Каждую минуту количество воды в каждой вещи уменьшается на единицу (если конечно же вещь не является полностью сухой). Когда количество воды в вещи становится нулевым, вещь становится сухой и ее можно упаковывать.
Каждую минуту Джейн может выбрать одну вещь, которую может положить на батарею. Батарея достаточно горячая, поэтому каждую минуту на ней вещь теряет k единиц воды (но не меньше нуля - если вещь содержит менее k единиц воды, то через минуту воды в ней будет ноль).
Задача состоит в том, чтобы минимизировать общее время сушки с помощью эффективного использования радиатора. Процесс сушки заканчивается, когда вся одежда сухая.
Входные данные
Первая строка содержит одно число n (1 ≤ n ≤ 105
). Вторая строка содержит числа ai
(1 ≤ ai
≤ 109
). В третьей строке находится число k (1 ≤ k ≤ 109
).
Выходные данные
Вывести одно число - наименьшее количество минут, за которое можно высушить все белье.
3 2 3 9 5
3
3 2 3 6 5
2