You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You are walking with your dog, and now you are at the promenade. The promenade can be represented as an infinite line. Initially, you are in the point $$$0$$$ with your dog.

You decided to give some freedom to your dog, so you untied her and let her run for a while. Also, you watched what your dog is doing, so you have some writings about how she ran. During the $$$i$$$-th minute, the dog position changed from her previous position by the value $$$a_i$$$ (it means, that the dog ran for $$$a_i$$$ meters during the $$$i$$$-th minute). If $$$a_i$$$ is positive, the dog ran $$$a_i$$$ meters to the right, otherwise (if $$$a_i$$$ is negative) she ran $$$a_i$$$ meters to the left.

During some minutes, you were chatting with your friend, so you don't have writings about your dog movement during these minutes. These values $$$a_i$$$ equal zero.

You want your dog to return to you after the end of the walk, so the destination point of the dog after $$$n$$$ minutes should be $$$0$$$.

Now you are wondering: what is the maximum possible number of different integer points of the line your dog could visit on her way, if you replace every $$$0$$$ with some integer from $$$-k$$$ to $$$k$$$ (and your dog should return to $$$0$$$ after the walk)? The dog visits an integer point if she runs through that point or reaches in it at the end of any minute. Point $$$0$$$ is always visited by the dog, since she is initially there.

If the dog cannot return to the point $$$0$$$ after $$$n$$$ minutes regardless of the integers you place, print -1.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3000; 1 \le k \le 10^9$$$) — the number of minutes and the maximum possible speed of your dog during the minutes without records.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of meters your dog ran during the $$$i$$$-th minutes (to the left if $$$a_i$$$ is negative, to the right otherwise). If $$$a_i = 0$$$ then this value is unknown and can be replaced with any integer from the range $$$[-k; k]$$$.

## Output Format
If the dog cannot return to the point $$$0$$$ after $$$n$$$ minutes regardless of the set of integers you place, print -1. Otherwise, print one integer — the maximum number of different integer points your dog could visit if you fill all the unknown values optimally and the dog will return to the point $$$0$$$ at the end of the walk.

## Examples
```input
3 2
5 0 -4
```
```output
6
```
-----
```input
6 4
1 -2 0 3 -4 5
```
```output
7
```
-----
```input
3 1000000000
0 0 0
```
```output
1000000001
```
-----
```input
5 9
-7 -3 8 12 0
```
```output
-1
```
-----
```input
5 3
-1 0 3 3 0
```
```output
7
```
-----
```input
5 4
0 2 0 3 0
```
```output
9
```

Now solve the problem and return the code.