{"problem":{"name":"D. Плохая многозадачность","description":{"content":"Спасать мир — задача не из легких, трудности возникают на каждом шагу. Так и сейчас, таки пробравшись в кабинет к Поппи Адамс, Эггси вновь попал в передрягу — на экране появилась сама Поппи и сказала,","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10155D"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nВ первой строке содержится два числа n и b — суммарное количество программ, запущенных на сервере, и максимальное количество операций, которое может выполниться на сервере за секунду (1 ≤ n ≤ 105, 1 ≤ b ≤ 109).В следующей строке содержится n чисел ai — количество операций для выполнения программы уничтожения и добавленных Эггси программ соответственно в порядке, в котором они расположены в очереди (1 ≤ ai ≤ 109).\n\n## Выходные Данные\n\nВ единственной строке выведите количество секунд, через которое программа уничтожения завершится.\n\n## Примеры\n\nВходные данные5 13 4 3 1 2Выходные данные10Входные данные4 26 2 5 1Выходные данные7\n\n## Примечание\n\nВо втором тестовом примере посекундная последовательность действий будет следующая:  1 секунда: первая программа (программа уничтожения) запускается на исполнение, выполняет 2 операции, а затем перемещается в конец очереди;  2 секунда: вторая программа запускается на исполнение, выполняет 2 операции, завершается и удаляется из очереди;  3 секунда: третья программа запускается на исполнение, выполняет 2 операции, а затем перемещается в конец очереди;  4 секунда: четвертая программа запускается на исполнение, выполняет 1 операцию, завершается и удаляется из очереди;  5 секунда: первая программа (программа уничтожения) запускается на исполнение, выполняет 2 операции, а затем перемещается в конец очереди;  6 секунда: третья программа запускается на исполнение, выполняет 2 операции, а затем перемещается в конец очереди;  7 секунда: первая программа (программа уничтожения) запускается на исполнение, выполняет 2 операции, завершается и удаляется из очереди. Дальнейшее выполнение программ нас не интересует, как видно, через 7 секунд программа уничтожения завершится.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10155D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}