CF1680D.Dog Walking

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.

你正和你的狗一起散步，现在你们来到了一条林荫道上。这条林荫道可以被建模为一条无限长的直线。初始时，你和你的狗都位于坐标 $0$ 处。

你决定给你的狗一些自由，于是解开了牵引绳，让她独自奔跑一段时间。同时，你一直在观察她的行动，并记录下了她每分钟的位移情况。在第 $i$ 分钟内，狗的位置相对于前一分钟改变了 $a_i$（即她在第 $i$ 分钟内跑了 $a_i$ 米）。若 $a_i > 0$，表示狗向右跑了 $a_i$ 米；若 $a_i < 0$，则表示狗向左跑了 $|a_i|$ 米。

在某些分钟里，你正在和朋友聊天，因此没有记录下狗在这些分钟内的移动情况。这些未记录的 $a_i$ 值被记为 $0$。

你希望狗在散步结束时回到你身边，即经过 $n$ 分钟后，狗最终所处的位置必须是 $0$。

现在你想知道：如果将每个 $0$ 替换为区间 $[-k, k]$ 内的某个整数（替换后狗仍需在 $n$ 分钟后回到 $0$），那么狗在整个过程中最多可能访问多少个不同的整数点？狗在某一整数点被视作“访问过”，当且仅当她在某次奔跑过程中经过该点，或在某分钟结束时恰好停在该点。注意，起点 $0$ 总是被访问的，因为狗初始就位于此处。

如果无论怎样将每个 $0$ 替换为 $[-k, k]$ 中的整数，都无法使狗在 $n$ 分钟后回到 $0$，则输出 -1。

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]$.

输入的第一行包含两个整数 $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]$ 内的任意整数。

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.

如果无论你如何放置整数，狗都无法在 $n$ 分钟后返回到点 $0$，则输出 $-1$；否则，输出一个整数——即在你最优地填充所有未知值、且狗最终恰好回到点 $0$ 的前提下，狗最多能够访问的不同整数点的个数。