Maximum Sum

Time Limit : 1 sec, Memory Limit : 65536 KB

最大の和

問題

n 個の整数からなる数列 a1, a2, ..., an と正整数 k (1 ≤ kn) が与えられる.このとき, 連続して並ぶ k 個の整数の和 Si = ai + ai+1 + ... + ai+k-1 (1 ≤ in - k + 1) の最大値を出力するプログラムを作りなさい.

入力

入力ファイルのファイル名は input.txt である. 1 行目には正整数 n (1 ≤ n ≤ 100000) と正整数 k (1 ≤ kn) がこの順に空白で 区切られて書かれている.2 行目以降の第 1 + i 行目 (1 ≤ in) には, 数列の i 番目の項 ai (-10000 ≤ ai ≤ 10000) が書かれている. 採点用データのうち, 配点の 60% 分は n ≤ 5000, k ≤ 1000 を満たす.

出力

出力ファイルのファイル名は output.txt である. output.txt は 1 行だけからなり,その 1 行は Si の最大値だけを含む.

入出力の例

input.txt

5 3
2
5
-4
10
3

output.txt

11

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数のデータセットが与えられます. データセットの終わりは2つのゼロを含む行で示されます.

Sample Input

5 3
2
5
-4
10
3
0 0

Sample Output

11

Source: 7th Japanese Olympiad in Informatics , 2007-02-12
http://www.ioi-jp.org/