你正在和你的狗一起散步,现在你在海滨长廊。长廊可以表示为一条无限长的线。最初,你和你的狗处于$$$0$$$的状态。
你决定给你的狗一些自由,所以你解开了她,让她跑了一会儿。另外,你观察了你的狗在做什么,所以你有一些关于她如何跑步的文章。在第 $$$i$$$ 分钟内,狗的位置与之前的位置相比改变了 $$$a_i$$$ 值(这意味着狗在第 $$$i$$$ 分钟内跑了 $$$a_i$$$ 米)。如果 $$$a_i$$$ 为正,则狗向右跑 $$$a_i$$$ 米,否则(如果 $$$a_i$$$ 为负)她向左跑 $$$a_i$$$ 米。
在几分钟内,您正在与您的朋友聊天,因此您没有关于您的狗在这段时间里的活动的记录。这些值 $$$a_i$$$ 为零。
您希望您的狗在步行结束后回到您身边,因此 $$$n$$$ 分钟后狗的目的地点应该是 $$$0$$$。
现在您想知道:如果您将每个 $$$0$$$ 替换为 $$$-k$$$ 到 $$$k$$$ 之间的某个整数(并且您的狗在散步后应该返回到 $$$0$$$),那么您的狗在路上可以访问的不同整数点的最大可能数量是多少?如果狗在任何分钟结束时跑过该点或到达该点,则该狗将访问该整数点。狗总是会访问 $$$0$$$ 点,因为她最初就在那里。
如果狗在 $$$n$$$ 分钟后无法返回点 $$$0$$$,则无论您放置的整数如何,都打印 -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]$$$。
输出
如果狗在 $$$n$$$ 分钟后无法返回点 $$$0$$$,则无论您放置的整数集如何,都打印 -1。否则,打印一个整数 - 如果您以最佳方式填充所有未知值,并且狗将在步行结束时返回到点 $$$0$$$,则您的狗可以访问的不同整数点的最大数量。
示例
输入 #1
3 2 5 0 -4
输出 #1
6
输入 #2
6 4 1 -2 0 3 -4 5
输出 #2
7
输入 #3
3 1000000000 0 0 0
输出 #3
1000000001
输入#4
5 9 -7 -3 8 12 0
输出#4
-1
输入 #5
5 3 -1 0 3 3 0
输出 #5
7
输入 #6
5 4 0 2 0 3 0
输出 #6
9