Walk

【题目描述】

小欣正在遛狗，但是在遛狗的过程中遇到了朋友，于是停了下来，然后想让小狗自由地跑动，于是松开了绳子（题目设定，公共场合遛狗须牵绳）。第 $i$ 分钟小狗会跑动 $a_i$ 米，向左跑 $a_i < 0$，向右跑 $a_i > 0$，但是小欣忘记了某些时候小狗跑动的距离，此时 $a_i = 0$。假设小狗开始跑动的点的下标为 $0$，小狗最后一定会跑回下标为 $0$ 的位置。现在你可以将所有的 $0$ 替换成任意 $-k$ 到 $k$ 之间的数（包括 $-k$ 和 $k$），在保证小狗最后能够回到原点的情况下，求出小狗走过的下标的最大数量，若最后无法回到原点输出 $-1$。

【输入格式】

从文件 walk.in 中读取数据

第一行两个整数 $n, k$，$1 \leq n \leq 3000$，$1 \leq k \leq 10^9$。

第二行 $n$ 个整数表示序列 $a$，$-10^9 \leq a_i \leq 10^9$。

【输出格式】

输出到文件 walk.out 中

一行一个整数表示小狗走过的下标的最大数量。

【输入样例】

3 2
5 0 -4

【输出样例】

6

【数据范围与约定】

• 对于前 $30\%$ 的数据，$n \leq 10$
• 存在 $10\%$ 的数据，仅有一个 $a_i$ 满足 $a_i = 0$，且序列初始为有序序列
• 对于 $100\%$ 的数据，没有特殊限制。

【样例解释】

只能将中间的 $0$ 替换成 $-1$。