题目描述

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

现在有 $\red{n}$ 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 $\red{1}$ 到 $\red{n}$ 编号，$\red{i}$ 号同学的接水量为 $\red{w_i}$。接水开始时，$\red{1}$ 到$\red{m}$ 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学$\red{j}$ 完成其接水量要求$\red{w_j}$ 后，下一名排队等候接水的同学$\red{k}$马上接替$\red{j}$ 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即$\red{j}$ 同学第$\red{x}$ 秒结束时完成接水，则$\red{k}$ 同学第$\red{x+1}$ 秒立刻开始接水。若当前接水人数$\red{n’}$不足$\red{m}$，则只有$\red{n’}$个龙头供水，其它$\red{m−n}’$个龙头关闭。

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

输入格式

第 $\red1$ 行$\red2$ 个整数$\red{n}$ 和$\red{m}$，用一个空格隔开，分别表示接水人数和龙头个数。

第$\red2$ 行 $\red{n}$ 个整数$\red{w_1、w_2、……、w_n}$，每两个整数之间用一个空格隔开，$\red{w_i}$ 表示$\red{i}$ 号同学的接水量。

输出格式

只有一行，$\red{1}$ 个整数，表示接水所需的总时间。

样例

输入样例1

5 3
4 4 1 2 1

输出样例1

4

输入输出样例1说明

第$\red1$ 秒，$\red3$ 人接水。第$\red1$ 秒结束时，$\red{1、2、3 }$号同学每人的已接水量为$\red{1，3}$号同学接完水，$\red4$ 号同学接替$\red3$ 号同学开始接水。

第$\red2$ 秒，$\red3$ 人接水。第$\red2$ 秒结束时，$\red{1、2}$ 号同学每人的已接水量为$\red{2，4}$号同学的已接水量为$\red1$。

第$\red3$ 秒，$\red3$ 人接水。第$\red3$ 秒结束时，$\red{1、2}$ 号同学每人的已接水量为$\red{3，4}$ 号同学的已接水量为$\red2$。$\red4$ 号同学接完水，$\red5$ 号同学接替$\red4$ 号同学开始接水。

第$\red4$ 秒，$\red3$人接水。第$\red4$秒结束时，$\red{1、2}$ 号同学每人的已接水量为$\red{4，5}$ 号同学的已接水量为$\red1$。$\red{1、2、5}$ 号同学接完水，即所有人完成接水。

总接水时间为$\red4$ 秒。

样例输入2

8 4
23 71 87 32 70 93 80 76

样例输出2

163

数据范围与提示

$\red{1 \leq n \leq 10000, }$

$\red{1 \leq m \leq 100,m \leq n,}$

$\red{1 \leq wi \leq 100}$