Sweet part-time job

Time limit1sMemory limit512 MB

Summary

Junsu can work at most m consecutive days out of n days with given daily wages; find the maximum total pay for such a window.

Level: Easy3 of 10
Topics: Sliding window, Prefix sum, Array
Solved: No attempts yet

Problem

Yunho owns a convenience store with an unusual pay scheme.

The amount of work differs from day to day, so the pay for each day is fixed in advance.
Yunho pays the exact daily wage on the same day it is earned.
He lets an employee work only the number of days agreed on.
He never hires anyone back after they quit. So once hired, you must work every day from your first day to your last, with no day off in between.

Junsu has to pay rent in $n+1$ days, so he wants a job at Yunho's store. From the pay records left by people who quit earlier, he learned the daily wage for every day from day 1 to day $n$ . He also has an exam to prepare for, so he can work at most $m$ days.

Junsu can work only on consecutive days. Find the largest amount he can earn.

Input

The first line contains the number of days left before rent is due, $n$ ( $1 \le n \le 100{,}000$ ), and the largest number of days Junsu can work, $m$ ( $0 \le m \le n$ ), separated by a space.

The second line contains the daily wages $T_i$ for day 1 through day $n$ in order ( $0 < T_i \le 1{,}000{,}000$ ).

Output

Print the largest amount Junsu can earn on one line.

Examples5

Example 1
Input
```
5 3
10 20 30 20 10
```
Expected output
```
70
```
Example 2
Input
```
1 1
1000000
```
Expected output
```
1000000
```
Example 3
Input
```
1 0
5
```
Expected output
```
0
```
Example 4
Input
```
4 4
1 2 3 4
```
Expected output
```
10
```
Example 5
Input
```
6 2
1 2 3 100 1 2
```
Expected output
```
103
```