题目背景

有一位刚学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。