← 返回题目列表

Codeforces · 1680/D

D. 遛狗

中文机器翻译题面 查看原题

你正在和你的狗一起散步,现在你在海滨长廊。长廊可以表示为一条无限长的线。最初,你和你的狗处于$$$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