Problem Background

Translated from ROIR 2022 D2T4.

Santa Claus allows Vova to choose a gift.

In front of Vova, there are $n$ gifts arranged in a row. Each gift brings Vova a certain level of happiness, represented by an integer, where the $i$-th gift has a value of $a_i$. The happiness values can be positive, negative, or zero.

Santa Claus instructs Vova to choose two integers $l$ and $r$, satisfying $1 \le l \le r \le n$. Vova needs to select all gifts from $l$ to $r$. However, among the selected gifts, Vova must give the $k$ gifts with the highest happiness values to his sister Masha.

Problem Description

Help Vova choose $l$ and $r$ such that $1 \le l \le r \le n, r - l + 1 \ge k$, and maximize the total happiness of the gifts he keeps (excluding those given to Masha).

Input Format

The first line contains two integers $n$ and $k$, representing the number of gifts in front of Vova and the number of gifts that need to be given to Masha, respectively.

The second line contains $n$ integers separated by spaces, where the $i$-th integer $a_i$ represents the happiness value of each gift.

Output Format

Output a single integer representing the total happiness of the gifts Vova keeps, excluding those given to Masha.

Sample Input and Output

Sample Input #1

5 0
2 -4 5 -1 7

Sample Output #1

11

Sample Input #2

5 1
2 -4 5 -1 7

Sample Output #2

4

Sample Input #3

5 2
2 -4 5 -1 7

Sample Output #3

0

Notes

In Sample 1, Vova does not need to give any gifts to Masha, so he will choose $l = 3, r = 5$, and the total happiness of the selected gifts is $5 + (-1) + 7 = 11$.

In Sample 2, Vova will need to give the gift with the highest happiness value to Masha. Then, he will still choose $l = 3, r = 5$, but the total happiness is $5 + (-1) = 4$.

In Sample 3, Vova needs to give the two gifts with the highest happiness values to Masha. In this case, it is不难发现 that Vova's best choice is to select only two gifts and give them all to Masha. An optimal choice is to select $l = 1, r = 2$. The total happiness is $0$.

This problem uses bundled testing.

For $100\%$ of the data, $1 \le n \le 200000, 0 \le k \le \min(100, n), -10^9 \le a_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分