/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
数直線上にリンゴが落ちてきます。
各 i=1,2,\ldots,N について、座標 i には A_i 個のリンゴが落ちてきます。それ以外の場所にはリンゴは落ちてきません。
あなたは幅 W のカゴを持っています。
整数 L を自由に選び、L を左端としてカゴを設置することで、座標 L 以上 L+W 未満の範囲に落ちてくるリンゴが全てカゴに入ります。
最大で何個のリンゴがカゴに入るようにできますか？
制約
- 1 \leq W \leq N \leq 10^6
- 0 \leq A_i \leq 10^3
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 3 3 1 4 1 5
出力例 1
10
L=3 とすると、座標 3,4,5 に落ちてくる 4+1+5=10 個のリンゴがカゴに入ります。これが最大です。
入力例 2
10 10 1 1 1 1 1 1 1 1 1 1
出力例 2
10
入力例 3
12 4 314 159 265 358 979 323 846 264 338 327 950 288
出力例 3
2506
Problem Statement
Apples are dropping onto a number line.
A_i apples will drop onto the coordinate i for each i=1,2,\ldots,N; no other apples will drop.
You have a basket of width W.
You may freely choose an integer L to place the basket, aligning its left end at L, so that it collects apples falling onto the coordinates between L and L+W-1, inclusive.
At most how many apples can you collect?
Constraints
- 1 \leq W \leq N \leq 10^6
- 0 \leq A_i \leq 10^3
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N W A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 3 3 1 4 1 5
Sample Output 1
10
If you set L=3, the basket collects 4+1+5=10 apples falling onto coordinates 3,4,5. This is the maximum.
Sample Input 2
10 10 1 1 1 1 1 1 1 1 1 1
Sample Output 2
10
Sample Input 3
12 4 314 159 265 358 979 323 846 264 338 327 950 288
Sample Output 3
2506