题目描述

xwj 的信奥赛课非常受欢迎，午休时同学们都要排队找老师答疑。这次学校请来了 $m$ 位老师同时答疑。

每位同学的答疑时长可能不同。每位老师面前排成一支队伍，同一支队伍里的同学依次答疑。一位同学的完成时间等于：他自己的答疑时长，加上在同一支队伍里排在他前面的所有同学的答疑时长之和。

请你把 $n$ 位同学分配到 $m$ 支队伍中，并安排好每支队伍内的先后顺序，使得所有同学的完成时间之和最小。请输出这个最小值。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示学生人数和老师（队伍）人数。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$，表示每位同学的答疑时长。

输出格式

输出一行一个整数，表示最小的总完成时间。

样例 1

4 2
2 3 1 2

11

样例 2

4 1
2 3 1 2

17

数据范围

对于所有测试数据，保证 $1 \le m \le n \le 10^5$，$1 \le t_i \le 10^4$。