Problem Description

On ftiasch's 18th birthday, lqp18_31 showed her a magical sequence $A_1$, $A_2$, ..., $A_N$. She is allowed to choose at most $M$ consecutive segments as her birthday gift.

Naturally, ftiasch wants to know the maximum possible sum of the selected elements. Can you help her?

Input Format

Line 1: Two integers $N$ ($1 \le N \le 10^5$) and $M$ ($0 \le M \le 10^5$), representing the length of the sequence and the number of segments that can be chosen.

Line 2: $N$ integers $A_1$, $A_2$, ..., $A_N$ ($0 \le \mid A_i \mid \le 10^4$), representing the sequence.

Output Format

One integer, representing the maximum sum.

5 2
2 1 -2 3 -2

6

Hint

Translated by ChatGPT 5