Вы гуляете со своей собакой и сейчас дошли до набережной. Набережная может быть представлена как бесконечная прямая. Изначально вы находитесь в точке \(0\) со своей собакой.
Вы решили предоставить немного свободы своей собаке, поэтому вы отвязали ее от поводка и дали ей немного побегать. Также вы смотрели, что собака делает, поэтому у вас есть некоторые записи с информацией о ее беге. В течение \(i\)-й минуты позиция собаки изменялась относительно ее предыдущей позиции на значение \(a_i\) (это значит, что собака пробежала \(a_i\) метров в течение \(i\)-й минуты). Если \(a_i\) положительно, собака пробежала \(a_i\) метров направо, иначе (если \(a_i\) отрицательно) она пробежала \(a_i\) метров налево.
В некоторые минуты вы переписывались в мессенджере со своим другом, поэтому у вас нет записей о передвижениях вашей собаки в эти минуты. Эти значения \(a_i\) равны нулю.
Вы хотите, чтобы ваша собака вернулась к вам в конце прогулки, поэтому последняя точка назначения собаки после \(n\) минут должна быть равна \(0\).
Вам стало интересно: чему равно максимально возможное количество различных целочисленных точек на прямой, которые могла посетить ваша собака, если вы замените каждый \(0\) на какое-то целое число от \(-k\) до \(k\) (и ваша собака обязана вернуться в \(0\) после прогулки)? Собака посещает целочисленную точку, если она пробегает мимо нее или встает в ней в конце любой минуты. Точка \(0\) всегда является посещенной, потому что она изначально находится в ней.
Если собака не может вернуться в точку \(0\) после \(n\) минут вне зависимости от того, как вы заполните пропуски, выведите -1.
Выходные данные
Если собака не может вернуться в точку \(0\) после \(n\) минут вне зависимости от того, как вы заполните пропуски, выведите -1. Иначе выведите одно целое число — максимальное количество различных целочисленных точек, которые ваша собака могла бы посетить, если бы вы заполнили пропуски оптимально, и собака вернулась бы в \(0\) в конце прогулки.