Vova 的房子是一个由 $$$n$$$ 元素组成的数组(是的,我认为这是第一个问题,有人住在数组中)。阵列的某些位置有加热器。如果 $$$i$$$ 位置有加热器,则数组的第 $$$i$$$ 元素为 $$$1$$$,否则数组的第 $$$i$$$ 元素为 $$$0$$$。
每个加热器都有一个值 $$$r$$$ ($$$r$$$ 对于所有加热器都是相同的)。该值意味着 $$$pos$$$ 位置处的加热器可以加热 $$$[pos - r + 1; 范围内的所有元件; pos + r - 1]$$$。
Vova 喜欢一边思考一边在他的房子里走来走去,他讨厌房子的寒冷位置。 Vova 希望打开他的一些加热器,这样他房子的每个部分都将由至少一个加热器加热。
Vova 的目标是加热整个房子(数组的所有元素),即如果 $$$n = 6$$$、$$$r = 2$$$ 且加热器位于 $$$2$$$ 和 $$$5$$$ 位置,那么如果 Vova 打开房子中的所有加热器,则可以加热整个房子(然后前 $$$3$$$ 元素将被加热)由第一个加热器加热,最后 $$$3$$$ 元件将由第二个加热器加热)。
最初,所有加热器都关闭。
但从另一方面来说,Vova 并不喜欢为电费支付太多费用。因此,他希望打开最少数量的加热器,以便他的房子的每个元件都至少由一个加热器加热。
你的任务是找到这个数量的加热器或者说不可能让整个房子变暖。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$r$$$ ($$$1 \le n, r \le 1000$$$) — 数组中的元素数量和加热器的值。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$) — Vova 的房屋描述。
输出
打印一个整数——加热整个房子所需的最少加热器数量,如果不可能的话,打印 -1。
示例
输入 #1
6 2 0 1 1 0 0 1
输出 #1
3
输入 #2
5 3 1 0 0 0 1
输出 #2
2
输入 #3
5 10 0 0 0 0 0
输出 #3
-1
输入#4
10 3 0 0 1 1 0 1 0 0 0 1
输出#4
3
注意
在第一个示例中,位于 $$$2$$$ 位置的加热器加热元件 $$$[1; 3]$$$,位置$$$3$$$的加热器加热元件$$$[2, 4]$$$,位置$$$6$$$的加热器加热元件$$$[5; 6]$$$ 所以答案是$$$3$$$。
在第二个示例中,位于 $$$1$$$ 位置的加热器加热元件 $$$[1; 3]$$$并且位于$$$5$$$位置的加热器加热元件$$$[3; 5]$$$ 所以答案是$$$2$$$。
在第三个示例中,没有加热器,因此答案为 -1。
在第四个示例中,位于 $$$3$$$ 位置的加热器加热元件 $$$[1; 5]$$$,$$$6$$$位置的加热器加热元件$$$[4; 8]$$$,$$$10$$$位置的加热器加热元件$$$[8; 10]$$$ 所以答案是$$$3$$$。