eolymp
bolt
Try our new interface for solving problems
Məsələlər

Сушка

Сушка

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

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

Джейн только что постирала n вещей. Во время стирки каждая из них набрала ai единиц воды. Каждую минуту количество воды в каждой вещи уменьшается на единицу (если конечно же вещь не является полностью сухой). Когда количество воды в вещи становится нулевым, вещь становится сухой и ее можно упаковывать.

Каждую минуту Джейн может выбрать одну вещь, которую может положить на батарею. Батарея достаточно горячая, поэтому каждую минуту на ней вещь теряет k единиц воды (но не меньше нуля - если вещь содержит менее k единиц воды, то через минуту воды в ней будет ноль).

Задача состоит в том, чтобы минимизировать общее время сушки с помощью эффективного использования радиатора. Процесс сушки заканчивается, когда вся одежда сухая.

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

Первая строка содержит одно число n (1n100 000). Вторая строка содержит числа ai (1ai109). В третьей строке находится число k (1k109)

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

Вывести одно число - наименьшее количество минут, за которое можно высушить все белье.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
2 3 9
5
Çıxış verilənləri #1
3
Giriş verilənləri #2
3
2 3 6
5
Çıxış verilənləri #2
2
Mənbə 2005 ACM NEERC, Northern Subregional Contest, Санкт-Петербург, Октябрь 29, Задача D