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个箱子里的小球数量,每两个数之间用空格分隔。
输出
输出一行一个正整数,表示所消耗的最小体力值。
样例
输入
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。
来源
云南编程挑战赛