[COCI2012-2013#3] AERODROM

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

输入共 $n+1$ 行。 第一行两个整数 $n,m$，分别表示服务台的个数和代表团的人数。 随后 $n$ 行，每行一个整数 $t_k$，表示第 $k$ 个服务台办理一名乘客的登记手续需要花费的时间。

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

2 6
7
10

28

7 10
3
8
3
6
9
2
4

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$ | **【题目来源】** 本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T4 AERODROM_**，按照原题数据配置，满分 $120$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。