题目背景

超市里有 $n$ 位顾客等着结账，收银台一共开了 $k$ 个。每位顾客买的东西多少不同，结账要花的时间也不一样。

题目描述

第 $i$ 位顾客结账需要 $t_i$ 的时间。顾客可以自由决定排在哪个收银台后面，超市也可以自由安排每位顾客在队伍里的先后顺序。

一个人从开始排队到他结完账所花的时间，等于排在他前面的所有人的结账时间之和，再加上他自己结账用的时间。

请你安排一个方案，使得所有顾客"从开始排队到结完账"所花的时间之和最小，输出这个最小值。

输入格式

第一行两个正整数 $n, k$，分别表示顾客人数和收银台数量。

第二行 $n$ 个正整数 $t_1, t_2, \ldots, t_n$，表示每位顾客结账需要的时间。

输出格式

一行，一个整数，表示最小的时间之和。

输入输出样例 #1

输入 #1

3 2
3 1 2

输出 #1

7

样例解释

一种最优安排是：$1$ 号收银台安排用时 $1$ 和 $2$ 的两位顾客（用时 $1$ 的排在前面），$2$ 号收银台安排用时 $3$ 的顾客。

三人的完成时间分别是 $1$、$3$、$3$，和为 $7$。可以证明没有比它更小的方案了。

说明/提示

• $1 \le n \le 100000$
• $1 \le k \le n$
• $1 \le t_i \le 10^6$
• 答案在 $64$ 位整数范围内