测试数据来自 system/1894

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H的 \(N\) 个精灵排成一行，方便起见依次编号为 1 到 \(N\)。精灵 \(i\) 的生命力为 \(s_i\)。她们的生命力可能参差不齐，所以小H决定把精灵们按原有顺序分成若干战斗小组。每一组可以包含任意不超过 \(K\) 个连续的精灵，并且一个精灵不能属于多于一个的战斗小组。由于精灵们会互相学习，一组中每一个精灵的生命力会变成这一组中最高精灵的生命力。

　　请帮助小H求出，在他合理地安排分组的情况下，可以达到的生命力之和的最大值。

【输入格式】

　　输入的第一行包含 \(N\) 和 \(K\)。
　　以下 \(N\) 行按照 \(N\) 个精灵的排列顺序依次给出她们的生命力。生命力是一个不超过 \(10^5\) 的正整数。

【输出格式】

　　输出小H通过将连续的精灵进行分组可以达到的最大生命力和。

【输入输出样例1】

　Input

7 3
1
15
7
9
2
5
10

　Output

84

【输入输出样例说明】

　　在这个例子中，最优的方案是将前三个精灵和后三个精灵分别分为一组，中间的精灵单独成为一组（注意一组的精灵数量可以小于 \(K\)）。即： [1 15 7] [9] [2 5 10] 。这样能够 有效地将 7 个精灵的生命力提高至 [15 15 15] [9] [10 10 10] ，三组精灵的生命力的和为: 15×3 + 9×1 + 10×3 = 84。

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤10000\)，\(1≤K≤1000\)。

【来源】

　　Mr.he