Description

Given a sequence of $n$ non-negative integers $a_1 ,\cdots, a_n$. You may choose some of them, but no more than $k$ consecutive numbers can be chosen. Your task is to maximize the sum of the chosen numbers.

Input Format

The first line contains two integers $n,k$.

The following $n$ lines each contain one integer, representing $a_i$.

Output Format

Output a single value representing the answer.

5 2
1
2
3
4
5 

12

Hint

For $20\%$ of the testdata, $n \le 10$.

For another $20\%$ of the testdata, $k=1$.

For $60\%$ of the testdata, $n \le 10^3$.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le k \le n$, $0 \le a_i \le 10^9$.

Time limit: 500 ms.

Translated by ChatGPT 5