Вы гуляете со своей собакой и сейчас дошли до набережной. Набережная может быть представлена как бесконечная прямая. Изначально вы находитесь в точке $$$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.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 3000; 1 \le k \le 10^9$$$) — количество минут и максимально возможная скорость вашей собаки в минуты с отсутствующими записями.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), где $$$a_i$$$ равно количеству метров, которые ваша собака пробежала в течение $$$i$$$-й минуты (влево, если $$$a_i$$$ отрицательно и направо, если оно положительно). Если $$$a_i = 0$$$, то это значение неизвестно и может быть заменено на любое целое число из отрезка $$$[-k; k]$$$.
Если собака не может вернуться в точку $$$0$$$ после $$$n$$$ минут вне зависимости от того, как вы заполните пропуски, выведите -1. Иначе выведите одно целое число — максимальное количество различных целочисленных точек, которые ваша собака могла бы посетить, если бы вы заполнили пропуски оптимально, и собака вернулась бы в $$$0$$$ в конце прогулки.
3 2 5 0 -4
6
6 4 1 -2 0 3 -4 5
7
3 1000000000 0 0 0
1000000001
5 9 -7 -3 8 12 0
-1
5 3 -1 0 3 3 0
7
5 4 0 2 0 3 0
9
