题目描述

有n个人排队到r个水龙头去打水，他们装满水桶所需的时间分别为$t_1,t_2,\ldots,t_n$。每个水龙头同一时刻只能供一个人打水。请合理安排每个人的打水顺序，使所有人的等待时间与打水时间之和最少。

输入格式

第一行输入两个整数n和r，分别表示人数和水龙头数量。

第二行输入n个整数，分别表示每个人装满水桶所需的时间。

输出格式

输出一个整数，表示所有人的等待时间与打水时间之和的最小值。

输入样例 1

6 2
5 4 6 2 1 7

输出样例 1

40

输入样例 2

1 1
6373

输出样例 2

6373

输入样例 3

2 2
5720 5030

输出样例 3

10750

数据范围

• $1\le r\le n\le 10000$。
• 每个人的打水时间 $t_i$ 满足 $1\le t_i\le 10000$。
• 答案在 64 位有符号整数范围内。