{"raw_statement":[{"iden":"statement","content":"Спасать мир — задача не из легких, трудности возникают на каждом шагу. Так и сейчас, таки пробравшись в кабинет к Поппи Адамс, Эггси вновь попал в передрягу — на экране появилась сама Поппи и сказала, что агент слишком предсказуем, и она как всегда на несколько шагов впереди, ведь запуск уничтожения антидота к вирусу, который она распространила, уже запущен, и ничто не может это остановить, мир будет уничтожен.\n\nОднако Эггси не просто так является агентом лучшей секретной службы, поэтому он сразу же достал свой ноутбук, вычислил IP-адрес сервера, на котором запущена программа уничтожения и взломал его. Оказалось, что это личный компьютер Поппи, а она не очень хорошо в них разбирается. Ее операционная система MS ADOS не поддерживает параллельное исполнение программ, поэтому все программы исполняются в одном потоке. Для этого поддерживается очередь задач на исполнение, и раз в секунду первая задача из очереди запускается на исполнение. За секунду программа может успеть сделать не более b операций. Если программа успевает выполнить все необходимые операции, она удаляется из очереди, иначе она переносится в конец очереди на дальнейшее выполнение.\n\nЭггси быстро был обнаружен, а на сервере сменили пароль, тем самым закрыв для него доступ к серверу. Однако перед этим он успел узнать, что программе для уничтожения нужно a1 операций для завершения, а также добавить в очередь задач на исполнение n - 1 других задач с a2, a3, ..., an операциями для выполнения соответственно. Теперь он хочет понять, сколько у него времени, чтобы добраться до Поппи, пока программа уничтожения не завершилась. Помогите ему найти количество секунд, которое потребуется программе уничтожения для завершения.\n\nВ первой строке содержится два числа n и b — суммарное количество программ, запущенных на сервере, и максимальное количество операций, которое может выполниться на сервере за секунду (1 ≤ n ≤ 105, 1 ≤ b ≤ 109).\n\nВ следующей строке содержится n чисел ai — количество операций для выполнения программы уничтожения и добавленных Эггси программ соответственно в порядке, в котором они расположены в очереди (1 ≤ ai ≤ 109).\n\nВ единственной строке выведите количество секунд, через которое программа уничтожения завершится.\n\nВо втором тестовом примере посекундная последовательность действий будет следующая:\n\nДальнейшее выполнение программ нас не интересует, как видно, через 7 секунд программа уничтожения завершится.\n\n"},{"iden":"входные данные","content":"В первой строке содержится два числа n и b — суммарное количество программ, запущенных на сервере, и максимальное количество операций, которое может выполниться на сервере за секунду (1 ≤ n ≤ 105, 1 ≤ b ≤ 109).В следующей строке содержится n чисел ai — количество операций для выполнения программы уничтожения и добавленных Эггси программ соответственно в порядке, в котором они расположены в очереди (1 ≤ ai ≤ 109)."},{"iden":"выходные данные","content":"В единственной строке выведите количество секунд, через которое программа уничтожения завершится."},{"iden":"примеры","content":"Входные данные5 13 4 3 1 2Выходные данные10Входные данные4 26 2 5 1Выходные данные7"},{"iden":"примечание","content":"Во втором тестовом примере посекундная последовательность действий будет следующая:  1 секунда: первая программа (программа уничтожения) запускается на исполнение, выполняет 2 операции, а затем перемещается в конец очереди;  2 секунда: вторая программа запускается на исполнение, выполняет 2 операции, завершается и удаляется из очереди;  3 секунда: третья программа запускается на исполнение, выполняет 2 операции, а затем перемещается в конец очереди;  4 секунда: четвертая программа запускается на исполнение, выполняет 1 операцию, завершается и удаляется из очереди;  5 секунда: первая программа (программа уничтожения) запускается на исполнение, выполняет 2 операции, а затем перемещается в конец очереди;  6 секунда: третья программа запускается на исполнение, выполняет 2 операции, а затем перемещается в конец очереди;  7 секунда: первая программа (программа уничтожения) запускается на исполнение, выполняет 2 операции, завершается и удаляется из очереди. Дальнейшее выполнение программ нас не интересует, как видно, через 7 секунд программа уничтожения завершится."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the total number of tasks in the queue.  \nLet $ b \\in \\mathbb{Z}^+ $ be the maximum number of operations executable per second.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of operation counts for each task, where $ a_1 $ is the operation count for the destruction program (first in queue).\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq b \\leq 10^9 $  \n3. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nSimulate the queue execution:  \n- Each second, the first task in the queue executes up to $ b $ operations.  \n- If the task’s remaining operations $ \\leq b $, it completes and is removed.  \n- Otherwise, it is moved to the end of the queue with remaining operations $ a_i - b $.  \n\nFind the number of seconds until the destruction program (initially at position 1) completes.","simple_statement":"You are given a queue of n programs, each needing a certain number of operations to finish.  \nEach second, the first program in the queue runs and completes up to b operations.  \nIf it finishes all its operations, it leaves the queue. Otherwise, it goes to the end of the queue.  \nYou need to find how many seconds it takes for the first program (the destruction program) to finish completely.","has_page_source":false}