Item 2

Time limit2sMemory limit1024 MB

Summary

Find the maximum sum of picked values when each interior picked run must span at least K positions, while runs touching either end of the line are exempt.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum, Array
Solved: No attempts yet

Problem

An infinitely long vertical line extends to the left and right, and $N$ items are placed on it. The $i$ -th item is at position $i$ and has value $A_i$ .

Juwon has tongs of length $K$ . Juwon chooses an integer coordinate $x$ ( $-10^9 \le x \le 10^9$ ), and the tongs pick up every item in the range from $x$ to $x+K-1$ . A picked item disappears from its position and cannot be put back. Juwon uses the tongs as many times as needed to make the total value of the picked items as large as possible.

Find the maximum total value Juwon can pick up. Juwon may never use the tongs, in which case the total value is 0.

Input

The first line contains the number of items $N$ and the tong length $K$ .

The second line contains the item values $A_1, A_2, \cdots, A_N$ in order, separated by spaces.

Output

Print the maximum total value of the picked items.

Constraints

$1 \le K \le N \le 500\,000$
$-500\,000 \le A_i \le 500\,000$ $(1 \le i \le N)$
All input numbers are integers.

Hint

The answer can exceed the 32-bit integer range, so C/C++ users should use the long long type, and Java users should use the long type.

Examples2

Example 1
Input
```
9 3
-2 3 -1 5 4 0 -10 5 -5
```
Expected output
```
11
```
Example 2
Input
```
5 5
1 -10 -10 -10 1
```
Expected output
```
2
```