时间限制：1 s　　内存限制：128 MB

题目描述

集训队里有 $n$ 名学员排成一排，从左到右依次编号为 $1,2,\dots,n$。第 $i$ 名学员的能力值为 $s_i$。

教练打算把学员分成若干个连续的小组进行合作训练。每个小组可以包含不超过 $K$ 名学员，且每名学员恰属于一个小组。

由于同组学员会互相交流，训练结束后，小组内每名学员的能力值都会变成该小组中最高的能力值。

请你帮助教练安排分组方案，使得训练结束后所有学员能力值之和最大。

输入格式

第一行两个整数 $n,K$，相邻整数之间用空格分隔。

第二行 $n$ 个整数 $s_1,s_2,\dots,s_n$，表示每名学员的能力值。

输出格式

输出一行一个整数，表示所有学员能力值之和的最大可能值。

样例 1

输入

7 3
1 15 7 9 2 5 10

输出

84

解释

最优分组为：$\{1,2,3\}$、$\{4\}$、$\{5,6,7\}$。

• 第一组最高能力值为 $15$，组内 3 人能力值均变为 $15$；
• 第二组仅学员 4，能力值保持 $9$；
• 第三组最高能力值为 $10$，组内 3 人能力值均变为 $10$。

总和为 $15\times3+9+10\times3=45+9+30=84$。注意每个小组的人数可以小于 $K$。

样例 2

输入

3 5
4 4 4

输出

12

数据范围与提示

对于 $100\%$ 的数据：

• $1\le n\le 10^4$；
• $1\le K\le 10^3$；
• $1\le s_i\le 10^5$。

提示：答案可能超过 32 位整数的范围，请使用 64 位整数。