flamethrower_ex

Potato wants to burn Po The Sloth's orchard (because Po owes him money and hasn't returned it to him for 2 weeks).

Po the Sloth's orchard contains a row of N trees, labelled from 1 to N from left to right. Potato has a flamethrower. This flamethrower can destroy a consecutive sequence of at most K trees. He can choose to destroy no trees at all.

Potato wants to cause as much damage as possible. He knows the cost of planting each tree. This can be negative because these trees have CCTVs on them, which means Potato will get sued and will lose money! Potato wants to aim his flamethrower in such a way that the sum of costs of trees he destroys is as high as possible. He wonders what this cost is.

Note

As this problem deals with large outputs, you are strongly advised to insert these 2 lines of code at the start of your main() function:

ios_base::sync_with_stdio(false);

cin.tie(NULL);

Input

The first line contains two integers, N and K.

The following line contains N integers. The i^th integer denotes the cost of the tree with label i.

Output

Output the maximum cost of the trees Potato can damage.

Constraints:

1 ≤ K ≤ N ≤ 10⁷

-10⁹ ≤ C_i ≤ 10⁹, where C_i denotes the cost of the i^th tree.

Subtasks

Subtask 1 (13%): 1 ≤ K ≤ N ≤ 1000, C_i is guaranteed to be positive.

Subtask 2 (18%): 1 ≤ K ≤ N ≤ 1000

Subtask 3 (27%): 1 ≤ K ≤ N ≤ 10⁶, C_i is guaranteed to be positive.

Subtask 4 (14%): 1 ≤ K ≤ N ≤ 10⁶

Subtask 5 (28%): No additional constraints

Subtask 6 (0%): Sample Testcases

Sample Input 1:

6 3
5 8 9 2 4 1

Sample Output 1:

22

Sample Explanation

Potato can destroy Trees 1 to 3 to obtain a total cost of 22. It can be proven that there exists no contiguous subarray with length ≤ 3 that has a sum of more than 22.

Sample Input 2:

5 2
10 -4 -5 3 0

Sample Output 2:

10

Sample Explanation

Potato can destroy Tree 1 to obtain a total cost of 10. Note that Potato does not need to destroy 2 trees, he just needs to destroy up to 2 trees.