← 返回题目列表

Codeforces · 965/D

D. 一次性石头

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

很多青蛙想要过河。河流的宽度为 $$$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$$$。