Description

Today is Xiao Z's birthday, and his classmates brought him a cake. The cake is a rectangular prism, divided into $n$ identical small pieces with different colors, and each small piece has a corresponding lucky value.

As the birthday person, Xiao Z naturally wants the sum of lucky values of the cake he eats to be as large as possible, but Xiao Z can eat at most $m(m\le n)$ small pieces of cake.

Please help him choose $k(1 \le k\le m)$ consecutive pieces among these $n$ pieces so that their total lucky value is maximized.

Formally, in the sequence $\{p_n\}$, find a subsegment $[l,r](r-l+1\le m)$ that maximizes $\sum\limits_{i=l}^rp_i$.

Input Format

The first line contains two integers $n,m$. They represent that there are $n$ small pieces in total, and Xiao Z can eat at most $m$ small pieces.

The second line contains $n$ integers. The $i$-th integer $p_i$ represents the lucky value of the $i$-th small piece of cake.

Output Format

Output a single integer in one line, which is the maximum lucky value Xiao Z can obtain.

5 2
1 2 3 4 5

9

6 3
1 -2 3 -4 5 -6

5

Hint

Constraints and Conventions.

• For $20\%$ of the testdata, $1\le n\le100$.
• For $100\%$ of the testdata, $1\le n\le5\times 10^5$, $|p_i|≤500$.

It is guaranteed that the absolute value of the answer is within $[0,2^{31}-1]$.

Translated by ChatGPT 5