{"raw_statement":[{"iden":"statement","content":"A lot of frogs want to cross a river. A river is $w$ units width, but frogs can only jump $l$ units long, where $l &lt; w$. Frogs can also jump on lengths shorter than $l$. but can't jump longer. Hopefully, there are some stones in the river to help them.\n\nThe stones are located at integer distances from the banks. There are $a_i$ stones at the distance of $i$ units from the bank the frogs are currently at. Each stone can only be used once by one frog, after that it drowns in the water.\n\nWhat is the maximum number of frogs that can cross the river, given that then can only jump on the stones?"},{"iden":"input","content":"The first line contains two integers $w$ and $l$ ($1 \\le l &lt; w \\le 10^5$) — the width of the river and the maximum length of a frog's jump.\n\nThe second line contains $w - 1$ integers $a_1, a_2, \\ldots, a_{w-1}$ ($0 \\le a_i \\le 10^4$), where $a_i$ is the number of stones at the distance $i$ from the bank the frogs are currently at."},{"iden":"output","content":"Print a single integer — the maximum number of frogs that can cross the river."},{"iden":"examples","content":"Input\n\n10 5\n0 0 1 0 2 0 0 1 0\n\nOutput\n\n3\n\nInput\n\n10 3\n1 1 1 1 2 1 1 1 1\n\nOutput\n\n3"},{"iden":"note","content":"In the first sample two frogs can use the different stones at the distance $5$, and one frog can use the stones at the distances $3$ and then $8$.\n\nIn the second sample although there are two stones at the distance $5$, that does not help. The three paths are: $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$."}],"translated_statement":[{"iden":"statement","content":"许多青蛙想要过河。河宽 $w$ 单位，但青蛙只能跳 $l$ 单位长，其中 $l < w$。青蛙也可以跳比 $l$ 短的距离，但不能跳更长。幸运的是，河里有一些石头可以帮助它们。\n\n石头位于距离河岸的整数位置处。在距离青蛙当前所在河岸 $i$ 单位的位置上有 $a_i$ 块石头。每块石头只能被一只青蛙使用一次，之后就会沉入水中。\n\n给定青蛙只能落在石头上，最多有多少只青蛙能够过河？\n\n第一行包含两个整数 $w$ 和 $l$ ($1 lt.eq l < w lt.eq 10^5$) —— 河的宽度和青蛙的最大跳跃长度。\n\n第二行包含 $w -1$ 个整数 $a_1, a_2, dots.h, a_(w -1)$ ($0 lt.eq a_i lt.eq 10^4$)，其中 $a_i$ 表示距离青蛙当前所在河岸 $i$ 单位处的石头数量。\n\n请输出一个整数 —— 能够过河的青蛙的最大数量。\n\n在第一个样例中，两只青蛙可以分别使用距离为 $5$ 的不同石头，一只青蛙可以使用距离为 $3$ 和随后 $8$ 的石头。\n\n在第二个样例中，尽管距离为 $5$ 的位置有两块石头，但这并无帮助。三条路径分别是：$0 arrow.r 3 arrow.r 6 arrow.r 9 arrow.r 10$，$0 arrow.r 2 arrow.r 5 arrow.r 8 arrow.r 10$，$0 arrow.r 1 arrow.r 4 arrow.r 7 arrow.r 10$。"},{"iden":"input","content":"第一行包含两个整数 $w$ 和 $l$ ($1 lt.eq l < w lt.eq 10^5$) —— 河的宽度和青蛙的最大跳跃长度。第二行包含 $w -1$ 个整数 $a_1, a_2, dots.h, a_(w -1)$ ($0 lt.eq a_i lt.eq 10^4$)，其中 $a_i$ 表示距离青蛙当前所在河岸 $i$ 单位处的石头数量。"},{"iden":"output","content":"请输出一个整数 —— 能够过河的青蛙的最大数量。"},{"iden":"examples","content":"输入10 50 0 1 0 2 0 0 1 0输出3输入10 31 1 1 1 2 1 1 1 1输出3"},{"iden":"note","content":"在第一个样例中，两只青蛙可以使用距离为 $5$ 的不同石头，一只青蛙可以使用距离为 $3$ 和随后 $8$ 的石头。在第二个样例中，尽管距离为 $5$ 的位置有两块石头，但这并无帮助。三条路径分别是：$0 arrow.r 3 arrow.r 6 arrow.r 9 arrow.r 10$，$0 arrow.r 2 arrow.r 5 arrow.r 8 arrow.r 10$，$0 arrow.r 1 arrow.r 4 arrow.r 7 arrow.r 10$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ w \\in \\mathbb{Z}^+ $ be the width of the river.  \nLet $ l \\in \\mathbb{Z}^+ $ be the maximum jump length, with $ 1 \\le l < w $.  \nLet $ A = (a_1, a_2, \\dots, a_{w-1}) $ be a sequence of non-negative integers, where $ a_i $ denotes the number of stones at distance $ i $ from the starting bank.\n\n**Constraints**  \n1. $ 1 \\le l < w \\le 10^5 $  \n2. $ 0 \\le a_i \\le 10^4 $ for all $ i \\in \\{1, 2, \\dots, w-1\\} $  \n\n**Objective**  \nFind the maximum number of frogs that can cross the river from position $ 0 $ to position $ w $, such that:  \n- Each frog makes a sequence of jumps, each of length at most $ l $.  \n- Each jump lands on an integer position $ i \\in \\{1, 2, \\dots, w-1\\} $ (stones), or directly to $ w $.  \n- Each stone at position $ i $ can be used by at most $ a_i $ frogs.  \n- Frogs may jump from position $ 0 $ to any position $ j \\in [1, l] $, and from any position $ i $ to any position $ j \\in [i+1, \\min(i+l, w)] $.  \n\nThe problem reduces to computing the **minimum cut** in a flow network where:  \n- Nodes represent positions $ 0, 1, 2, \\dots, w $.  \n- There is a directed edge from $ i $ to $ j $ if $ 0 < j - i \\le l $ and $ j \\le w $.  \n- Each node $ i \\in \\{1, 2, \\dots, w-1\\} $ has capacity $ a_i $ (stone limit).  \n- Nodes $ 0 $ and $ w $ have infinite capacity.  \n\nThe maximum number of frogs is equal to the **minimum cut** between node $ 0 $ and node $ w $, where the cut separates the graph into two sets: reachable from $ 0 $ and unreachable, and the cut capacity is the sum of stone capacities $ a_i $ for nodes $ i $ in the \"source side\" that have outgoing edges to the \"sink side\".\n\nEquivalently, due to the structure of the graph (only forward jumps of at most $ l $), the maximum flow equals the **minimum sum of $ a_i $ over any sliding window of $ l $ consecutive positions** from $ 1 $ to $ w-1 $, because any valid path must pass through at least one stone in every consecutive block of $ l $ positions.\n\nThus, define:  \n$$\nS_k = \\sum_{i=k}^{k+l-1} a_i \\quad \\text{for } k \\in \\{1, 2, \\dots, w - l\\}\n$$\n\nThen the maximum number of frogs is:  \n$$\n\\min_{k=1}^{w - l} S_k\n$$","simple_statement":null,"has_page_source":false}