题目描述

作为学校的一分子，智智最近遇到了一个难题：学校里有一个水房，水房里一共装有 $m$ 个龙头，每秒钟的供水量相等，均为 1。

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

接水规则如下：

• 开始时，前 $1$ 到 $m$ 号同学各占一个水龙头，同时接水。
• 当某名同学 $j$ 完成其接水量 $w_j$ 后，下一名排队等候的同学 $k$ 立即接替 $j$ 的位置开始接水，换人瞬间完成，无水浪费。
• 若当前接水人数 $n'$ 小于 $m$，则只有 $n'$ 个龙头供水，其余关闭。

请问所有同学接完水需要多少秒？

输入格式

• 第 1 行：两个整数 $n$ 和 $m$（1 ≤ $n$ ≤ 10000，1 ≤ $m$ ≤ 100 且 $m ≤ n$），用空格隔开
• 第 2 行：$n$ 个整数 $w_1, w_2, …, w_n$（1 ≤ $w_i$ ≤ 100），表示每个同学的接水量，用空格隔开

输出格式

• 一行，一个整数，表示接水所需的总时间（秒）

输入样例 #1

5 3
4 4 1 2 1

输出样例 #1

4

输入样例 #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 秒。