EOJ Monthly 2021.1 Sponsored by TuSimple
E. 菜品制作
单点时限: 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$。
通知
比赛状态发生变化，点 OK 刷新。
通知