我奶茶呢

题目描述

小 R 老师曾答应正在刷某构造题单的同学们：谁第一个到达 $10$ 题，就奖励他一杯奶茶。

在大家还在题单里苦苦构造的时候，P2441M 以迅猛之势率先到达了 $10$ 题。于是当天晚上有人请喝奶茶时，小 R 老师十分守信，直接把自己那杯奶茶给了 P2441M。

本来事情到这里应该已经结束了。

然而，一旁的 X 老师也十分大方，把自己的那杯奶茶给了 zhuyihao20100712。

直到晚上 $20:00$，小 R 老师再次打开榜单，忽然像发现了什么重大事件一般，盯着排行榜沉默了三秒：

第二名，好像是 xm，zhuyihao20100712，区区第三。

为了严厉打击“奶茶归属不清、奖励发放混乱”的行为，也为了贯彻“按排名发奶茶很公平吧”的原则，小 R 老师在 $0.1\text{s}$ 内当即做出决定：把 zhuyihao20100712 手里的那杯奶茶转交给 xm。

zhuyihao20100712 看着空空如也的双手，陷入了沉思：

我奶茶呢？

沉思结束后，zhuyihao20100712 认为，既然自己的奶茶已经被转交出去了，那再去买一杯新的，似乎也是非常合理的事情。

可惜此时夜色已深，最近的一家奶茶店又恰好在河对岸。为了赶在同学们全都回去睡觉之前买到奶茶，zhuyihao20100712 强行拉上了一群同学，带着唯一的手电筒，准备连夜过桥。

这座桥一次最多允许 $c$ 个人同时通过。由于天色已晚，所有人共用一个手电筒。每次过桥时，过桥的人中必须至少有一人携带手电筒。若若干人同时过桥，本次过桥所需时间等于这些人中单独过桥时间的最大值。

最开始，所有人和手电筒都在桥的左侧。虽然 zhuyihao20100712 对奶茶十分执着，但被强行拉来的同学们显然只想早点结束这一切回去睡觉。因此，他需要安排若干次过桥，使得所有人最终都到达桥的右侧，并且手电筒也在右侧。

你能帮他算出，最少需要多久才能把这群困得不行的同学送到河对岸吗？

输入格式

第一行包含两个整数 $n,c$，分别表示人数和桥一次最多允许同时通过的人数。

第二行包含 $n$ 个整数 $t_1,t_2,\ldots,t_n$，其中 $t_i$ 表示第 $i$ 个人单独过桥所需时间。

输出格式

输出一行一个整数，表示所有人都到达桥右侧所需的最小总时间。

样例 1 输入

4 6
1 2 10 5

样例 1 输出

10

样例 1 解释

桥一次可以容纳所有人，因此所有人一起过桥即可，总时间为最慢者所需的时间 $10$。

样例 2 输入

4 2
1 2 10 5

样例 2 输出

17

样例 2 解释

一种最优方案如下：

1. 用时为 $1,2$ 的两人过桥，花费 $2$；
2. 用时为 $1$ 的人返回，花费 $1$；
3. 用时为 $5,10$ 的两人过桥，花费 $10$；
4. 用时为 $2$ 的人返回，花费 $2$；
5. 用时为 $1,2$ 的两人过桥，花费 $2$。

总时间为：

$$2+1+10+2+2=17$$

样例 3

见选手目录下的 bridge/bridge3.in 与 bridge/bridge3.ans。

该样例满足子任务 $1$ 的约束条件。

样例 4

见选手目录下的 bridge/bridge4.in 与 bridge/bridge4.ans。

该样例满足子任务 $2$ 的约束条件。

样例 5

见选手目录下的 bridge/bridge5.in 与 bridge/bridge5.ans。

该样例满足子任务 $3$ 的约束条件。

样例 6

见选手目录下的 bridge/bridge6.in 与 bridge/bridge6.ans。

该样例满足子任务 $4$ 的约束条件。

样例 7

见选手目录下的 bridge/bridge7.in 与 bridge/bridge7.ans。

该样例满足子任务 $5$ 的约束条件。

样例 8

见选手目录下的 bridge/bridge8.in 与 bridge/bridge8.ans。

该样例满足子任务 $6$ 的约束条件。

样例 9

见选手目录下的 bridge/bridge9.in 与 bridge/bridge9.ans。

该样例满足子任务 $6$ 的约束条件，且 $n$ 达到数据范围上界，$c=9999$ 接近上界。

数据范围

对于所有测试数据，均满足：

• $2\le n,c\le 10^4$；
• $1\le t_i\le 10^9$。

本题共 $6$ 个子任务，采用捆绑测试。

子任务编号	分值	约束条件
$1$	$5$	$c\ge n$
$2$	$18$	$n\le 20$
$3$	$12$	$c=2$
$4$	$5$	所有 $t_i$ 均相同
$5$	$20$	$n\le 100$
$6$	$40$	无额外限制