4043. 菜品制作

单点时限: 1.0 sec

内存限制: 256 MB

Cuber QQ 去一家餐馆打工,他的任务是做 $k$ 道同样的菜。

我们知道,做一道菜可能需要多个工序,例如洗菜、切菜、烧菜。显然我们不能先切菜再洗菜,所以工序需要按顺序执行。

Cuber 要做的这道菜共有 $n$ 个工序,第 $i$ 个工序需要 $a_i$ 分钟才能完成。然而,依次完成这些菜品对 Cuber 来说太慢了。他准备使用自己的能力------分身术。Cuber 会变出 $k$ 个分身,第 $i$ 个分身将完成第 $i$ 道菜。

但这时 Cuber 发现了一个问题:每个工序需要的设备只有一处。例如,炉灶只有一个,所以两个 Cuber 的分身不能同时烧菜。Cuber 想知道,他的分身们至少需要多少分钟才能完成所有菜品。

输入格式

第一行两个整数 $n, k$($1 \le n \le 10^5, 1 \le k \le 10^9$)。

第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$($1 \le a_i \le 10^9$)。

输出格式

一行一个整数,表示答案。

样例

Input
3 3
10 10 10
Output
50
Input
2 2
1 2
Output
5

提示

对于样例一,工作分配如下:

其中绿色线段表示工序 $1$,橙色线段表示工序 $2$,紫色线段表示工序 $3$。

对于样例二,工作分配如下:

其中绿色线段表示工序 $1$,橙色线段表示工序 $2$。

245 人解决,285 人已尝试。

251 份提交通过,共有 790 份提交。

2.4 EMB 奖励。

创建: 3 月,3 周前.

修改: 3 月,1 周前.

最后提交: 3 天,8 小时前.

来源: EOJ Monthly 2021.1

题目标签