3. Красная Шапочка на болоте
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Красная Шапочка отправилась на болото для сбора клюквы, чтобы испечь пирожки для бабушки. Клюквенное болото представляет собой координатную прямую. Берег, на котором стоит девочка, имеет координату $$$0$$$, а клюквенная поляна — координату $$$N+1$$$. В точках с координатами $$$1, 2, \dots, N$$$ расположены кочки. Первоначально у девочки $$$E$$$ единиц энергии. Красная Шапочка может прыгнуть из точки $$$x$$$ в точку $$$y$$$ ($$$x \lt y$$$), потратив на это $$$(y-x)$$$ единиц энергии, то есть затраченная энергия равна расстоянию между кочками. После того, как девочка приземлится на кочке с координатой $$$i$$$, она получает $$$a_i$$$ единиц энергии (при этом значение $$$a_i$$$ может оказаться отрицательным, тогда энергия Красной Шапочки уменьшится при приземлении). Нельзя, чтобы энергия Красной Шапочки в какой-либо момент оказалась меньше нуля. Например, Красная Шапочка не может прыгнуть с кочки $$$1$$$ на кочку $$$3$$$, имея одну единицу энергии, вне зависимости от того, сколько энергии она получит на $$$3$$$-й кочке, так как для осуществления такого прыжка необходимо две единицы энергии.

Так как Красной Шапочке ещё надо вернуться обратно, девочке интересно, какое максимальное количество энергии у неё может оказаться, когда она достигнет поляны (точки с координатой $$$N+1$$$).

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

Первая строка входных данных содержит целое число $$$E$$$ — первоначальный запас энергии Красной Шапочки, $$$1 \leq E \leq 10^9$$$.

Вторая строка входных данных содержит целое число $$$N$$$ — количество кочек на болоте, $$$1\le N\le 500\,000$$$.

Следующие $$$N$$$ строк содержат по одному целому числу $$$a_i$$$ — энергия, которую получает Красная Шапочка на $$$i$$$-й кочке, $$$-2000 \leq a_i \leq 2000$$$.

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

Программа должна вывести одно число — максимальное количество единиц энергии, которое останется у Красной Шапочки после достижения клюквенной поляны. Если девочка не сможет достигнуть цели, выведите одно число «-1» (без кавычек).

Система оценки

Решения, правильно работающие при $$$N \leq 15$$$, будут оцениваться в 20 баллов.

Решения, правильно работающие при $$$N \leq 900$$$, будут оцениваться в 70 баллов.

Решения, правильно работающие, когда все $$$a_i \geq 0$$$, будут набирать не менее 20 баллов.

Примеры
Входные данные
2
3
1
-1
1
Выходные данные
0
Входные данные
1
4
-1
100
-1
-1
Выходные данные
-1
Примечание

В первом примере три кочки и первоначально 2 единицы энергии у Красной Шапочки. Она прыгает на кочку 1, что требует 1 единицу энергии, и у неё остаётся 1 единица энергии. На кочке 1 девочка получает 1 единицу энергии, и у неё становится 2 единицы энергии. Затем она прыгает с кочки 1 на кочку 3, потратив 2 единицы энергии, и у неё становится 0 энергии. Приземлившись на кочку 3, Красная Шапочка получает 1 единицу энергии, этого достаточно, чтобы перепрыгнуть с кочки 3 на поляну в точке 4, после чего у Красной Шапочки останется 0 единиц энергии.

Во втором примере у Красной Шапочки первоначально только 1 единица энергии, поэтому она может прыгнуть только на кочку 1, но значение $$$a_1=-1$$$, то есть после приземления на кочку 1 у Красной Шапочки энергия станет отрицательной, и она не сможет продолжить свой путь.