该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

我们有 $N$ 个箱子，每个箱子有自己的重量 $w_i$，每次我们可以将至多 $M$ 个箱子合并成一个重量为这几个箱子重量和的箱子，花费的体力是这合并的几个箱子的重量和。请问我们将这所有的箱子合并成一个箱子所需要花费的最少体力是多少？

输入格式

从文件 box.in 中读取数据。

第一行，两个正整数 $N$ ，$M$ ，表示有 $N$ 个箱子，每次操作至多可以合并 $M$ 个箱子。

第二行，$N$ 个正整数，表示这 $N$ 个箱子每个箱子的重量。

输出格式

输出到文件 box.out 中。

输出一个正整数，表示我们最少需要花费的体力是多少。

3 2
1 2 3

9

7 3
1 2 3 4 5 6 7

49

3 3
1 2 3

6

样例输入输出 4

见 4.in 与 4.ans

数据规模与约定

• 对于 $30\%$ 的数据，$2 \leq M \leq N \leq 10^3$。

• 对于 $100\%$ 的数据，$2 \leq M \leq N \leq 10^5$，每个箱子的重量 $1 \leq w_i \leq 10^6$。