drink.in/out

题目描述

天上捞有一个自助饮料机，机器上有$m$个饮料口供客人接饮料，每个饮料口流量相等，均为1个单位。

现在有 $n$ 个客人准备接饮料喝，他们排好了队，所以初始接饮料顺序已经确定，将这些客人按接饮料的顺序从 $1$ 到 $n$ 编号， $i$号客人的接水量为 $w_i$。接饮料开始时，$1$ 到 $m$ 号客人各占一个饮料口，并同时打开开关接饮料。当其中某位客人 $j$ 完成其接水量后，下一名排队等候的客人会立马补位，这个换人过程是瞬间完成的。即第 $j$ 位客人在第 $x$ 秒结束时完成饮料接取，则第 $k$ 名客人在第 $x + 1$秒立刻续上。 若当前接饮料的人数 $n$ 不足 $m$，则只有 $n$个饮料口供饮料，其他 $m - n$ 个饮料口关闭。

现在给出 $n$ 名客人的饮料需求量，按照上述接饮料规则，问所有客人都接完饮料需要多少秒。

输入格式

第一行两个整数 $n$ 和 $m$，用一个空格隔开，分别表示接饮料人数和饮料口个数。

第二行 $n$ 个整数 $w_1,w_2,\ldots,w_n$，每两个整数之间用一个空格隔开，$w_i$ 表示 $i$ 号客人的饮料需求量。

输出格式

一个整数，表示接饮料所需的总时间。

样例 #1

样例输入 #1

5 3
4 4 1 2 1

样例输出 #1

4

样例 #2

样例输入 #2

8 4
23 71 87 32 70 93 80 76

样例输出 #2

163

提示

【输入输出样例 #1 说明】

第 $1$ 秒，$3$ 人接水。第 $1$ 秒结束时，$1,2,3$ 号客人每人的已接水量为 $1,3$ 号客人接完水，$4$ 号客人接替 $3$ 号客人开始接水。

第 $2$ 秒，$3$ 人接水。第 $2$ 秒结束时，$1,2$ 号客人每人的已接水量为 $2,4$ 号客人的已接水量为 $1$。

第 $3$ 秒，$3$ 人接水。第 $3$ 秒结束时，$1,2$ 号客人每人的已接水量为 $3,4$ 号客人的已接水量为 $2$。$4$ 号客人接完水，$5$ 号客人接替 $4$ 号客人开始接水。

第 $4$ 秒，$3$ 人接水。第 $4$ 秒结束时，$1,2$ 号客人每人的已接水量为 $4,5$ 号客人的已接水量为 $1$。$1,2,5$ 号客人接完水，即所有人完成接水的总接水时间为 $4$ 秒。

【数据范围】

$1 \le n \le {10}^4$，$1 \le m \le 100$，$m \le n$；

$1 \le w_i \le 100$。