测试数据来自 b6e0_OJ/1007

题目背景

有一位刚学OI的蒟蒻，编程累了，准备出去活动活动。

题目描述

他找来了$n$堆石子，想把它们合成一堆。每一堆石子有一个重量$w_i$。每次可以选择任意不大于$m$堆石子合并，每次合并需要花费的精力是合并的所有石子的重量和（也就是合并后那一堆石子的重量）。如果他花费的精力太多他就不会去合并，所以他想知道最小需要花费多少精力。

输入格式

$n$ $m$
$w_i$ $w_2$ $w_3$ ... $w_n$

输出格式

最小需要花费的精力。

输入输出样例

输入

5 3
1 2 3 4 5

输出

21

样例解释

先合并1 2 3得到6，花费6精力；再合并4 5 6得到15，花费15精力，总精力是6+15=21。

数据范围

对于数据点1，$n≤10$，$m=2$。
对于数据点2~3，$n≤10$。
对于数据点4~5，$m=2$。
对于所有数据点，$2≤n,m≤100,000$，$1≤w_i≤1,000,000,000$。

贡献者

题面：b6e0。
数据：b6e0。