题目描述

有 $n$ 个人到 $r$ 个水龙头去打水，他们装满水桶的时间 $t_1, t_2, \dots, t_n$ 为整数且互不相等。应如何安排他们的打水顺序，才能使所有人花费的总时间最少？

每个人花费的时间 = 他等待的时间 + 他自己打水的时间。总花费时间为所有人花费的时间之和。

输入格式

第一行包含两个整数 $n, r$，分别表示人数和水龙头个数。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$，表示每个人打水需要的时间。

输出格式

一个整数，表示最少的总花费时间。

样例

3 2
1 2 3

7

样例 1 解释

最优安排：水龙头 1 依次打水 $1, 3$；水龙头 2 打水 $2$。
第一个人花费 $1$，第二个人花费 $2$，第三个人等待 $1$ 后打水 $3$ 花费 $4$。
总花费时间 $= 1 + 2 + 4 = 7$。

7 4
234 78 54 33 123 43 87

782

数据范围与提示

• 对于 $80\%$ 的数据：$1 \le n \le 10$；
• 对于 $100\%$ 的数据：$1 \le n \le 500$，$1 \le r \le 75$，$1 \le t_i \le 100$。