题目描述

童程学校原来只有一台饮水机，同学们只能排队打水，消耗了课间时间。学校决定改善设备，增加到了r台饮水机。但是老师还是想知道，学生们按照一个顺序去打水，总的花费时间最少，这样不是更节省时间吗？现在，有 n 个同学排队到 r 台饮水机去打水，他们装满水杯的时间 t~1~、t~2~...t~n~，这些数为整数，应如何安排他们的打水顺序才能使他们总共花费的时间最少？

输入格式

第一行 n，r (n≤300,r≤100) 第二行为 n 个同学打水所用的时间 t~i~ ( t~i~≤30)

输出格式

最少的花费时间

4 2
3 2 1 2

11

提示

数据范围与提示： n≤300，r≤100，t~i~≤30