0947 - 最小和部分列

問題

長さ $N$ の整数列 $A$ = { $a_1$, $a_2$, ... , $a_N$ } があります。

YDKは、その中から長さ $L$ の連続した部分列を1つ取り出します。

たとえば、 { $1$, $7$, $3$, $2$, $0$ } のうち長さ $3$ の部分列は

• { $1$, $7$, $3$ }
• { $7$, $3$, $2$ }
• { $3$, $2$, $0$ }

の3パターンがあります。

YDKは取り出した部分列の各要素の総和が最小になるようにしたいです。

そこで、そのように取り出した時の部分列の総和の最小値を求めるプログラムを作ってください。

入出力形式

入力

1行目に、整数列の長さ $N$ と取り出す部分列の長さ $L$ が空白区切りで与えられる。

以下、$N$ 行にわたって $a_i$ (1 ≤ $i$ ≤ $N$) が改行区切りで入力される。

N L
a1
a2
 :
aN

出力

取り出す部分列の総和が最小になるように取り出したときの総和を出力せよ。改行を忘れずに。

制約

• 1 ≤ $L$ ≤ $N$ ≤ 10⁶
• -10¹² ≤ $a_i$ ≤ 10¹²

入出力例

入力例1

5 3
1
7
3
2
0

出力例1

5

長さ $3$ の部分列の総和は、

• $1 + 7 + 3 = 11$
• $7 + 3 + 2 = 12$
• $3 + 2 + 0 = 5 $

の3パターンがあり、 $5$ が最小なので $5$ を出力する。

入力例2

4 2
3
-10
-8
9

出力例2

-18

入力例3

3 1
314159265358
271828182846
141421356237

出力例3

141421356237

入力が32bit整数型に収まらないことがあるので注意。