Красная Шапочка на болоте
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Красная Шапочка отправилась на болото для сбора клюквы, чтобы испечь пирожки для бабушки. Клюквенное болото представляет собой координатную прямую. Берег, на котором стоит Шапочка, имеет координату 0, а клюквенная поляна координату N+1. В точках с координатами 1, 2, ……, NN расположены кочки. Первоначально у девочки E единиц энергии. Красная Шапочка может прыгнуть из точки xx в точку y (x<y), потратив на это (y−x) единиц энергии, то есть количество единиц затраченной энергии равно расстоянию между кочками. После того как девочка приземлится на кочке с координатой i, она получает aiai единиц энергии (при этом значение aiai может оказаться отрицательным, тогда энергия Красной Шапочки уменьшится при приземлении). Нельзя, чтобы энергия Красной Шапочки в какой‑либо момент оказалась меньше нуля. Например, Красная Шапочка не может прыгнуть с кочки 1 на кочку 3, имея одну единицу энергии, вне зависимости от того, сколько энергии она получит на 3-й кочке, так как для осуществления такого прыжка необходимо две единицы энергии.
Так как Красной Шапочке ещё надо вернуться обратно, девочке интересно, какое максимальное количество энергии у неё может оказаться, когда она достигнет поляны (точки с координатой N+1).
Формат входных данных
Первая строка входных данных содержит целое число E первоначальный запас энергии Красной Шапочки, 1≤E≤109.
Вторая строка входных данных содержит целое число N количество кочек на болоте, 1≤N≤5×105.
Следующие N строк содержат по одному целому числу ai энергия, которую получает Красная Шапочка на i-й кочке, −2000≤ai≤2000.
Формат выходных данных
Программа должна вывести одно число максимальное количество единиц энергии, которое останется у Красной Шапочки после достижения клюквенной поляны. Если девочка не сможет достигнуть цели, выведите одно число «−1» (без кавычек).
Система оценки
Решения, правильно работающие при N≤15, будут оцениваться в 20 баллов.
Решения, правильно работающие при N≤900, будут оцениваться в 70 баллов.
Решения, правильно работающие, когда все ai≥0, будут набирать не менее 20 баллов.
Замечание
В первом примере три кочки и первоначально 2 единицы энергии у Красной Шапочки. Она прыгает на кочку 1, что требует 1 единицу энергии, и у неё остаётся 1 единица энергии. На кочке 1 девочка получает 1 единицу энергии, и у неё становится 2 единицы энергии. Затем она прыгает с кочки 1 на кочку 3, потратив 2 единицы энергии, и у неё становится 0 энергии. Приземлившись на кочку 3, Красная Шапочка получает 1 единицу энергии, этого достаточно, чтобы перепрыгнуть с кочки 3 на поляну в точке 4, после чего у Красной Шапочки останется 0 единиц энергии.
Во втором примере у Красной Шапочки первоначально только 1 единица энергии, поэтому она может прыгнуть только на кочку 1, но значение a1=−1, то есть после приземления на кочку 1 у Красной Шапочки энергия станет отрицательной и она не сможет продолжить свой путь.
Ввод
2
3
1
-1
1
Вывод
0
Ввод
1
4
-1
100
-1
-1
Вывод
-1