很多青蛙想要过河。河流的宽度为 $$$w$$$ 单位,但青蛙只能跳跃 $$$l$$$ 单位长,其中 $$$l < w$$$。青蛙也可以跳到比 $$$l$$$ 短的长度。但不能跳得更远。希望河里有一些石头可以帮助他们。
石头距离河岸整数距离。距离青蛙当前所在的河岸 $$$i$$$ 单位的距离处有 $$$a_i$$$ 石头。每块石头只能被一只青蛙使用一次,之后就会淹死在水中。
如果青蛙只能跳到石头上,最多可以有多少只青蛙过河?
输入
第一行包含两个整数 $$$w$$$ 和 $$$l$$$ ($$$1 \le l < w \le 10^5$$$) — 河流的宽度和青蛙跳跃的最大长度。
第二行包含 $$$w - 1$$$ 整数 $$$a_1, a_2, \ldots, a_{w-1}$$$ ($$$0 \le a_i \le 10^4$$$),其中 $$$a_i$$$ 是距离青蛙当前所在的银行 $$$i$$$ 处的石头数量。
输出
打印一个整数——可以过河的青蛙的最大数量。
示例
输入 #1
10 5 0 0 1 0 2 0 0 1 0
输出 #1
3
输入 #2
10 3 1 1 1 1 2 1 1 1 1
输出 #2
3
注意
在第一个示例中,两只青蛙可以使用距离 $$$5$$$ 处的不同石头,一只青蛙可以使用距离 $$$3$$$ 处的石头,然后是 $$$8$$$ 处的石头。
在第二个样本中,尽管距离 $$$5$$$ 处有两块石头,但这没有帮助。这三个路径是:$$$0 \to 3 \to 6 \to 9 \to 10$$$、$$$0 \to 2 \to 5 \to 8 \to 10$$$、$$$0 \to 1 \to 4 \to 7 \to 10$$$。