​3、包装礼物​​（​​​gift​**）**

**【题目描述】 **

在 Farmer John 最喜欢的节日里，他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。

Farmer John 的 N头奶牛排成一行，方便起见依次编号为1…N。奶牛 i 的包装礼物的技能水平为 si。她们的技能水平可能参差不齐，所以 FJ 决定把她的奶牛们分成小组。

每一组可以包含任意不超过 K 头的连续的奶牛，并且一头奶牛只能在一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平。请帮助 FJ 求出，在他合理地安排分组的情况下，所有奶牛可以达到的技能水平之和的最大值。

**【输入格式】 **

输入的第一行包含 N 和 K。

接下来 N 行按照 N 头奶牛的排列顺序依次给出她们的技能水平si。技能水平是一个不超过 10^5 的正整数。

**【输出格式】 **

输出奶牛可以达到的最大技能水平和。

【输入​​样例​**】**

7 3

1

15

7

9

2

5

10

【输出样例】

84

【样例1 说明】

在样例1中，最优的方案是将第1,2,3头奶牛分为一组，第4头奶牛分为一组，第5,6,7头奶牛分为一组（注意一组的奶牛数量可以小于 K）。这样能够有效地将 7 头奶牛的技能水平提高至 15、15、15、9、10、10、10，和为 84。

【数据范围】

对于10%的数据有 1≤N，K≤10。

对于30%的数据有 1≤N≤1000，1≤K≤100。

对于40%的数据有 1≤N≤2000，1≤K≤100。

对于100%的数据有1≤N≤10^4，1≤K≤10^3。