Батарейка героя

В игре у героя есть батарейка ёмкости C. В начале она полностью заряжена.

Дальше происходит n событий. Каждое событие меняет заряд на число d_i:

• если d_i отрицательное — это расход энергии;
• если d_i положительное — это подзарядка.

После каждого события заряд не может превышать C (лишняя энергия «пропадает»). Если после события заряд стал 0 или меньше — батарейка разрядилась, и игра заканчивается прямо на этом событии.

Нужно определить, на каком по счёту событии игра закончится. Если батарейки хватит на все события — вывести 0.

Формат ввода

В первой строке записаны два целых числа n и C. Во второй строке записаны n целых чисел d_1, d_2, ..., d_n.

Формат вывода

Выведите одно целое число — номер события, на котором батарейка разрядится (нумерация с 1), либо 0, если этого не случится.

Ограничения

• 1 ≤ n ≤ 2000
• 1 ≤ C ≤ 1_000_000
• -1000 ≤ d_i ≤ 1000

Пример

Ввод:

5 10
-3 -4 2 -6 -1

Вывод:

4

Ключевое наблюдение: каждое событие влияет только на текущий заряд, а ограничение заряд ≤ C действует сразу после изменения. Значит, ничего «умнее» хранить не нужно — достаточно честно симулировать процесс слева направо.

Почему работает симуляция: правило одинаковое для каждого шага, и момент окончания игры определяется первым событием, после которого заряд стал <= 0. Это именно «первое нарушение», его удобно ловить во время прохода.

План решения:

• Считай n, C и массив изменений d[1..n].
• Заведи переменную b = C (текущий заряд).
• Для i от 1 до n:
• Обнови заряд: b += d[i].
• Если заряд стал больше ёмкости, обрежь сверху: b = min(b, C).
• Если b <= 0, сразу выведи i и остановись.
• Если прошли все события и ни разу не разрядились — выведи 0.

Мини-сниппет для шага: b += d[i] b = min(b, C)

Сложность: O(n) по времени и O(1) по памяти.

Частая ошибка: проверять b <= 0 до обрезки min(b, C) или вообще забыть про обрезку сверху. По условию лишняя энергия пропадает сразу после события, поэтому порядок важен: сначала прибавили d[i], потом ограничили сверху, и только затем проверяем разряд (хотя для <=0 обрезка не спасает, привычка к правильному порядку убережёт от похожих задач).