多窗口排队

题目描述

服务大厅有 $k$ 个窗口，编号 $1$ 到 $k$。某一时刻有 $n$ 位顾客同时到达，他们按编号 $1$ 到 $n$ 的顺序依次选择窗口：每位顾客都会选择「当前已被分配的总服务时间最少」的窗口，如果有多个窗口并列最少，则选择编号最小的那个；选定后该窗口的总服务时间增加这位顾客需要的服务时间 $t_i$。同一个窗口同一时刻只能服务一位顾客。

请计算所有顾客都服务完毕的时刻，也就是全部窗口总服务时间的最大值。

输入格式

第一行两个整数 $n$ 与 $k$。

第二行 $n$ 个整数 $t_1, t_2, \dots, t_n$。

输出格式

一行一个整数，表示所有顾客都服务完毕的时刻。

样例

输入样例

4 2
3 1 4 2

输出样例

5

样例解释

前两位顾客分别去 $1$、$2$ 号窗口（都是 $0$，取编号小的）；第三位顾客去 $2$ 号窗口（总时间 $1$ 更小），累计 $5$；第四位顾客去 $1$ 号窗口（总时间 $3$ 更小），累计 $5$。最大值为 $5$。

数据范围

$1 \le n \le 2 \times 10^5$，$1 \le k \le n$，$1 \le t_i \le 10^4$。