题目描述

学校里有一个水房，水房里一共有 $m$ 个水龙头可供同学们打开水，每个水龙头每秒钟的供水量相等，均为 $1$。

现在有 $n$ 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 $1$ 到 $n$ 编号，$i$ 号同学的接水量为 $w_i$。

接水开始时，$1$ 到 $m$ 号同学各占一个水龙头，并同时打开水龙头接水。当某名同学完成接水后，下一名排队等候的同学马上接替他的位置开始接水。这个换人的过程瞬间完成，且没有任何水的浪费。

若当前接水人数不足 $m$，则只有正在接水的水龙头供水，其余水龙头关闭。

现在给出 $n$ 名同学的接水量，按照上述规则，求所有同学都接完水需要多少秒。

输入格式

第一行输入两个整数 $n,m$，分别表示接水人数和水龙头个数。

第二行输入 $n$ 个整数 $w_1,w_2,\dots,w_n$，其中 $w_i$ 表示第 $i$ 名同学的接水量。

输出格式

输出一行一个整数，表示接水所需的总时间。

样例

5 3
4 4 1 2 1

4

样例解释

第 $1$ 秒结束时，$3$ 号同学接完水，$4$ 号同学接替他开始接水。

第 $3$ 秒结束时，$4$ 号同学接完水，$5$ 号同学接替他开始接水。

第 $4$ 秒结束时，$1,2,5$ 号同学都接完水，所有人完成接水，总时间为 $4$ 秒。

数据范围

$1 \le n \le 10000$，$1 \le m \le 100$ 且 $m \le n$，$1 \le w_i \le 100$。

来源

NOIP 复赛