当前没有测试数据。

题目描述

在一场盛大的职业技能大赛中，$N$ 名工程师按编号顺序排列，他们的编号从 $1$ 到 $N$。

每位工程师有技能水平值 $P_i$，表示其可以在大赛中表现出的技能水平。为了提升团队协作效果，大赛允许工程师们自发组成若干小组参赛。

分组要求每个小组由不超过 $M$ 名、连续编号的工程师组成，且每位工程师只能属于一个参赛小组。在一个小组内，工程师们会相互学习，所有工程师的技能水平将统一提升至该小组中技能水平最高的工程师的技能水平。

请帮助工程师们设计一种最优的小组划分方案，使得所有工程师分组后的技能水平值之和最大化，从而在技能大赛中取得最佳总成绩。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $M$，分别表示工程师数量和每个小组的最大人数。

接下来的 $N$ 行，每行包含一个正整数 $P_i$，按工程师编号顺序表示其技能水平值。

输出格式

输出一个整数，表示通过合理划分小组，所有工程师能达到的最大技能水平值之和。

样例 #1

输入

7 3
1
15
7
9
2
5
10

输出

84

样例 #2

输入

12 3
10
1
9
2
3
5
12
8
1
9
23
18

输出

170

样例说明

样例 1 解释

工程师技能水平值：$[1, 15, 7, 9, 2, 5, 10]$，最大小组人数 $M = 3$。

一种最优划分方案：

• 小组 1：工程师 1 到 3（技能水平 $[1, 15, 7]$），最高技能水平 $15$，调整后为 $[15, 15, 15]$，贡献 $15 \times 3 = 45$。
• 小组 2：工程师 4（技能水平 $[9]$），最高技能水平 $9$，贡献 $9 \times 1 = 9$。
• 小组 3：工程师 5 到 7（技能水平 $[2, 5, 10]$），最高技能水平 $10$，调整后为 $[10, 10, 10]$，贡献 $10 \times 3 = 30$。

总技能水平之和：$45 + 9 + 30 = 84$。

数据范围

对于 $10\%$ 的数据，满足 $1 \le N \le 10$，$1 \le M \le 6$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^4$，$1 \le M \le 10^3$，$1 \le P_i \le 10^5$。