题目描述

$N$ 个人要打水，有 $M$ 个水龙头。第 $i$ 个人打水所需时间为 $T_i$。

请安排一个合理的方案，使得所有人的等待时间之和尽量小。

输入格式

第一行输入两个正整数 $N,M$。

第二行输入 $N$ 个正整数 $T_i$。

输出格式

输出一个整数，表示最小的等待时间之和。不需要输出具体的安排方案。

样例

7 3
3 6 1 4 2 5 7

11

样例解释

一种最佳打水方案是，将 $N$ 个人按照 $T_i$ 从小到大的顺序依次分配到 $M$ 个龙头打水。

样例中，$T_i$ 从小到大排序为 $1,2,3,4,5,6,7$。将他们依次分配到 $3$ 个龙头：

• 第一个龙头：$1,4,7$，等待时间和为 $0+1+(1+4)=6$；
• 第二个龙头：$2,5$，等待时间和为 $0+2=2$；
• 第三个龙头：$3,6$，等待时间和为 $0+3=3$。

所以总等待时间为 $6+2+3=11$。

数据范围

$N,M \le 1000$，$T_i \le 1000$。

来源

蓝桥杯练习系统