题目描述

由 $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$ 个测试点。各个测试点的数据范围如下表所示：

【题目来源】

本题来源自 COCI 2012-2013 CONTEST 3 T4 AERODROM，按照原题数据配置，满分 $120$ 分。

由 Eason_AC 翻译整理提供。