时间限制：1秒　　内存限制：256M

---

题目描述

由 \(m\) 人组成的某国代表团正前往澳大利亚参加 2013 年的 IOI。他们目前正在机场排队等候办理登机手续。有 \(n\) 个办理登机手续的服务台开放。一些官员的工作效率比其他官员高，所以服务台的运作速度不同。在第 \(k\) 个服务台，完成一名乘客的登机手续需要 \(t_k\) 秒，而我们的代表团成员恰好知道确切的数字。在开始时，所有的服务都做好接受下一名乘客的准备，而现在只允许我们的代表团成员排队。一个人只有在所有排在他前面的人都已经离开队列（**开始办理登机手续，不一定要完成**）时，才能占据一个可用的服务台开始办理登机手续。这时，这个人可以立即占据一张空闲的服务台（如果有的话），但也可以选择等待另一个办理登记手续更快的服务台变成空闲。

我们的代表团成员是计算机科学怪才，他们决定让他们所有人都尽快完成签到，你的任务是找到完成签到所需要花费的最短时间。

输入格式

输入共 \(n+1\) 行。

第一行两个整数 \(n,m\)，分别表示服务台的个数和代表团的人数。

随后 \(n\) 行，每行一个整数 \(t_k\)，表示第 \(k\) 个服务台办理一名乘客的登记手续需要花费的时间。

输出格式

输出仅一行一个整数，表示完成签到所需要花费的最短时间（单位为秒）。

输入输出样例 #1

输入 #1

2 6
7
10

输出 #1

28

输入输出样例 #2

输入 #2

7 10
3
8
3
6
9
2
4

输出 #2

8

说明/提示

【样例 1 解释】

对于样例 \(1\)，有两个服务台，处理时间分别为 \(7\) 秒和 \(10\) 秒。在代表团的六个人中，前两个人立即占据了这两个服务台。在第 \(7\) 秒，第一张桌子变成空闲，第三个人占据了它。在第 \(10\) 秒，第四个人占据了第二个服务台。在第 \(14\) 秒，第五个人占据了第一个服务台。在第 \(20\) 秒，第二张桌子再次变成空闲，但第六个人决定再等一秒钟（至第 \(21\) 秒），让第一张桌子空出来，然后占据它。这样一来，签到只要花费 \(28\) 秒就能完成了。如果第六个人没有等待更快的服务台，签到将花费 \(30\) 秒。

【数据范围】

本题一共 \(8\) 个测试点。各个测试点的数据范围如下表所示：

测试点编号	\(n\leqslant\)	\(m\leqslant\)	\(t_k\leqslant \)
\(1\sim 5\)	\(10^5\)	\(3\times 10^5\)	\(10^9\)
\(6\sim 8\)	\(10^5\)	\(10^9\)	\(10^9\)