Description

有N个人拿着大小各不相同的桶，排队到R个水龙头打水，每个人打满水旋即离开。其灌满桶需要的时间分别为整数T1，T2，...，Tn。请安排一个打水顺序，使每个人打水及等待耗时总和为最小？

例如：N=4，R=2；T1=2，T2=6，T3=4，T4=5。

则先让n1、n3先打，耗费T1、T3时间，后让n2接着n1打，耗费T1+T2时间，而n4接着n3打，耗费T3+T4时间，各人打水及等待时间为：T1+T1+T2 + T3+T3+T4 = 2+2+6 + 4+4+5 = 23，多种方案筛选，发现23最小。

Input

多组数据，每组数据以整数N（<=100）和R（<=10）开始，后跟N个不同整数，表示第i（1<=i<=N）个桶灌满的分钟数。

Output

对于每组数据，输出一行整数，表示每个人花费的打水和等待时间总和的最小分钟数。

Sample

Input

4 2
2 6 4 5

Output

23

Source: 2019-20-1期中考