题目描述

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

每个人打水的时间 = 排队的时间 + 实际打水的时间，本题假设一个人打好水，排在他后面的人接着打水的这个切换过程不消耗时间。

比如，有 $2$ 个人 A 和 B，他们打水的时间分别是 $3$ 和 $2$，只有 $1$ 个水龙头。如果 A 先打水，B 后打水，那么 A 打水的时间为 $3$，B 打水的时间为 $3+2$（B 排队 $3$ 分钟）。所有人打水的总时间就是每个人打水的时间之和。

输入格式

第一行，两个整数 $n$ 和 $r$（$1 \le n \le 500$，$1 \le r \le 100$）。
第二行，$n$ 个正整数 $t_1, t_2, \dots, t_n$（$1 \le t_i \le 1000$），表示每个人装满水桶的时间。

输出格式

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

样例

4 2
2 6 4 5

23

数据范围与提示

• $1 \le n \le 500$，$1 \le r \le 100$
• $1 \le t_i \le 1000$