9150 - 取小球(ball)

明明和妈妈一起去逛街,看见一个科学博览会,明明很想进去参观学习,但想进去需要先通过门口的关卡才可以拿到门票。这让明明感到有点困难,因为关卡上的知识明明没有学过。你能帮助明明通过关卡,拿到门票吗?

博览会门口的关卡信息如下:

在物理上有一个很神奇的现象:一根羽毛和一个铁球从比萨斜塔上同一高度同时落下,羽毛和铁球会在同一时间落地(忽略外在所有导致误差的因素)。李老师想在实验室验证这一现象的真实性,但他还差一个重要的实验器材,就是不同重量的球。

由于实验室器材有限,需要从n个实验箱里拿取小球,然后再组成其他重量的大球。小球重量均相等,并假设拿到的小球可以组成一个更重的大球。实验室的实验器材保管员告诉李老师:他可以把所有小球都拿走,但是需要先把所有小球都合并到一个实验箱里才能拿走。他每次至少需要合并2个箱子里的小球,最多只能合并k个箱子里面的小球,箱子里面的小球每次合并都必须一起被合并。每只箱子里面的小球数目已经贴在箱子外面,分别为a_1,a_2,...,a_n个,李老师可以清楚的看到。

李老师每合并一次所花费的体力为本次合并的所有小球的数量之和。请你帮助明明告诉李老师,拿走所有小球,所消耗的最小体力值。这样明明就能通过关卡,拿到门票。

输入

输入的第一行包含两个正整数nkn表示箱子的个数, k表示一次最多能合并k个箱子里的小球,nk之间用空格隔开。 输入的第二行包含n个正整数a_i,(i=1,2,...,n)表示第i个箱子里的小球数量,每两个数之间用空格分隔。

输出

输出一行一个正整数,表示所消耗的最小体力值。

样例

输入

3 3
29 25 56 

输出

110

输入

7 3
45 13 12 16 9 5 22

输出

199

提示

【样例1解释】

输入共有3个箱子,每次合并最多能合并3个箱子里的小球。将小球数量为29、25、56的箱子里的小球进行合并,消耗体力值为:29+25+56=110,所有小球已合并到一个箱子中,故答案为110.

【数据范围】

对于 30% 的数据,n\le 100

对于 60% 的数据,n\le 500

对于 100% 的数据,n\le 1000,1\le a_i\le 100,2\le k\le 10

来源

云南编程挑战赛

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题