题目描述

琦琦的学校每到下课，饮水机总是会排满了前来打水学生。 有 $\red{n（}$$\red{1<=n<=300000）}$个学生排队打水。第 $\red{i }$个学生打水需要 $\red{t_i（}$$\red{1<=t_i<=1000000）}$的时间。 每个学生需要等待他前面的所有学生打完水才能开始打水，请你安排一个打水的顺序，使得所有学生的等待时间的总和 $\red{T }$最小 。 输出这个等待总时间$\red{T}$。 当然，一台饮水机是完全不够的，为此，学校共修了 $\red{m（}$$\red{1<=m<=300000）}$台饮水机。

输入格式

第一行，两个整数，分别是 $\red{n，}$$\red{m}$。 第二行，$\red{n }$个整数，第 $\red{i }$个整数表示第 $\red{i }$个学生的打水时间 $\red{t_i}$。

输出格式

共一行，第一行，一个整数 最小的等待总时间 $\red{T}$。

样例

输入样例

4 1
4 3 2 1

输出样例

10