Спасать мир — задача не из легких, трудности возникают на каждом шагу. Так и сейчас, таки пробравшись в кабинет к Поппи Адамс, Эггси вновь попал в передрягу — на экране появилась сама Поппи и сказала, что агент слишком предсказуем, и она как всегда на несколько шагов впереди, ведь запуск уничтожения антидота к вирусу, который она распространила, уже запущен, и ничто не может это остановить, мир будет уничтожен.
Однако Эггси не просто так является агентом лучшей секретной службы, поэтому он сразу же достал свой ноутбук, вычислил IP-адрес сервера, на котором запущена программа уничтожения и взломал его. Оказалось, что это личный компьютер Поппи, а она не очень хорошо в них разбирается. Ее операционная система MS ADOS не поддерживает параллельное исполнение программ, поэтому все программы исполняются в одном потоке. Для этого поддерживается очередь задач на исполнение, и раз в секунду первая задача из очереди запускается на исполнение. За секунду программа может успеть сделать не более b операций. Если программа успевает выполнить все необходимые операции, она удаляется из очереди, иначе она переносится в конец очереди на дальнейшее выполнение.
Эггси быстро был обнаружен, а на сервере сменили пароль, тем самым закрыв для него доступ к серверу. Однако перед этим он успел узнать, что программе для уничтожения нужно a1 операций для завершения, а также добавить в очередь задач на исполнение n - 1 других задач с a2, a3, ..., an операциями для выполнения соответственно. Теперь он хочет понять, сколько у него времени, чтобы добраться до Поппи, пока программа уничтожения не завершилась. Помогите ему найти количество секунд, которое потребуется программе уничтожения для завершения.
В первой строке содержится два числа n и b — суммарное количество программ, запущенных на сервере, и максимальное количество операций, которое может выполниться на сервере за секунду (1 ≤ n ≤ 105, 1 ≤ b ≤ 109).
В следующей строке содержится n чисел ai — количество операций для выполнения программы уничтожения и добавленных Эггси программ соответственно в порядке, в котором они расположены в очереди (1 ≤ ai ≤ 109).
В единственной строке выведите количество секунд, через которое программа уничтожения завершится.
5 1
3 4 3 1 2
10
4 2
6 2 5 1
7
Во втором тестовом примере посекундная последовательность действий будет следующая:
Дальнейшее выполнение программ нас не интересует, как видно, через 7 секунд программа уничтожения завершится.