9150 - 取小球（ball）

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

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

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

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

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

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

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

【样例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。

云南编程挑战赛