题目描述

译自 ROI Regional 2022 Day2 T4. Подарки

圣诞老人让沃瓦选择新年礼物。

沃瓦面前有一排 $n$ 个礼物。每个礼物都有一个整数值，第 $i$ 个礼物的值为 $a_i$，表示这个礼物能给沃瓦带来的快乐值。快乐值可以是正数、负数或零。

圣诞老人让沃瓦选择两个数 $l$ 和 $r$，满足 $1 \le l \le r \le n$，并拿走从第 $l$ 个到第 $r$ 个的所有礼物。然而，沃瓦必须将选中的礼物中快乐值最大的 $k$ 个礼物送给他的妹妹玛莎。剩下的礼物沃瓦自己留下。

沃瓦希望选择 $l$ 和 $r$，使得他自己得到的礼物的总快乐值最大。礼物的总快乐值是这些礼物的 $a_i$ 值的总和。

请帮助沃瓦选择 $l$ 和 $r$，使得 $1 \le l \le r \le n$，$r - l + 1 \ge k$，并且沃瓦自己得到的礼物的总快乐值最大。

输入格式

第一行包含两个整数 $n$ 和 $k$ $(1 \le n \le 2\cdot 10^5, 0 \le k \le \min(100, n))$，表示沃瓦面前的礼物数量和需要送给玛莎的礼物数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^9 \le a_i \le 10^9)$，表示每个礼物的快乐值。

输出格式

输出一个整数，表示沃瓦自己得到的礼物的总快乐值。

5 0
2 -4 5 -1 7

11

在样例 1 中，沃瓦不需要给玛莎任何礼物，所以他会选择 $l = 3$，$r = 5$，他得到的礼物的总快乐值为 $5 + (-1) + 7 = 11$。

5 1
2 -4 5 -1 7

4

在样例 2 中，沃瓦需要给玛莎一个快乐值最大的礼物。他仍然会选择 $l = 3$，$r = 5$，但他得到的礼物的总快乐值为 $5 + (-1) = 4$。

5 2
2 -4 5 -1 7

0

在样例 3 中，沃瓦需要给玛莎两个快乐值最大的礼物。在这种情况下，最优选择是 $l = 1$，$r = 2$。

数据范围与提示

详细子任务附加限制及分值如下表所示。