Dragon

Interview

Time limit1sMemory limit1024 MB

Summary

Pick two disjoint blocks of at most K consecutive heads each in a row of N heads to maximize the total fire power removed.

Level: Medium6 of 10
Topics: Dynamic programming, Prefix sum, Sliding window, Array
Solved: No attempts yet

Problem

The legendary Slavic hero Ilya Muromets battles a legendary dragon.

The dragon has $N$ heads, numbered $1, 2, \dots, N$ from left to right. Like any dragon, it can breathe fire; the fire power of the $i$ -th head is $F_i$ .

With a single swing of his sword, Muromets can cut off up to $K$ consecutive heads. After a swing, the remaining heads close ranks and again form a single consecutive row.

Right now the dragon is dazed, so Muromets manages to make two swings in a row. Find the maximum total fire power that Muromets can eliminate with these two swings.

Input

The first line contains two space-separated integers: the number of heads $N$ and Muromets's maximum reach $K$ ( $1 \le N \le 200\,000$ , $1 \le K \le 200\,000$ ).

The second line contains $N$ space-separated integers $F_i$ , the fire power of each head ( $1 \le F_i \le 2000$ , $i = 1, \dots, N$ ).

Output

Output a single integer: the maximum total fire power that Muromets can eliminate with the two swings.

Examples2

Example 1
Input
```
8 2
1 3 3 1 2 3 11 1
```
Expected output
```
20
```
Example 2
Input
```
4 100
10 20 30 40
```
Expected output
```
100
```