Олимпиадный тренинг

Задача . E. Супергеройская битва


Задача

Темы: математика *1700

Супергерой сражается с монстром. Битва состоит из раундов, каждый из которых длится ровно \(n\) минут. Как только заканчивается очередной раунд, тут же начинается следующий, и так далее.

Каждый раунд проходит по одному и тому же сценарию. Этот сценарий описывается последовательностью из \(n\) целых чисел \(d_1, d_2, \dots, d_n\) (\(-10^6 \le d_i \le 10^6\)), где \(i\)-й элемент обозначает, что жизненная сила монстра (его hp) изменяется на величину \(d_i\) за \(i\)-ю минуту раунда. Формально, если в начале \(i\)-й минуты раунда жизненная сила монстра была равна \(h\), то сразу после окончания \(i\)-й минуты она изменяется следующим образом \(h := h + d_i\).

Начальная жизненная сила монстра равна \(H\). Это означает, что перед битвой его hp равен \(H\). Выведите первую минуту битвы, после которой монстр умрёт. Монстр умирает, если его hp становится равен или меньше \(0\). Выведите -1, если битва будет продолжаться бесконечно.

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

В первой строке записаны два целых числа \(H\) и \(n\) (\(1 \le H \le 10^{12}\), \(1 \le n \le 2\cdot10^5\)). Вторая строка содержит последовательность целых чисел \(d_1, d_2, \dots, d_n\) (\(-10^6 \le d_i \le 10^6\)), где \(d_i\) — это изменение hp монстра в \(i\)-ю минуту каждого раунда.

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

Выведите -1, если герой не сможет убить монстра, и битва будет продолжаться бесконечно. В противном случае выведите положительное целое число \(k\) такое, что \(k\) — это первая минута, после которой монстр мёртв.


Примеры
№Входные данныеВыходные данные
1
1000 6
-100 -200 -300 125 77 -4
9
2
1000000000000 5
-1 0 0 0 0
4999999999996
3
10 4
-3 -6 5 4
-1
Статистика успешных решений по компиляторам
 Кол-во
С++5