题目描述

$n$ 名同学按固定顺序排队接水，有 $m$ 个水龙头，每个每秒出水 $1$。第 $i$ 名同学需要 $w_i$ 单位的水。一开始队首的 $m$ 人同时接水；有人接完后，队首等待的人立即使用空出的水龙头。不能改变队伍顺序，求所有人接完水的时间。

输入格式

第 1 行2 个整数 n 和 m，用一个空格隔开，分别表示接水人数和龙头个数。 第 2 行 n 个整数 w1、w2、……、wn，每两个整数之间用一个空格隔开，wi表示 i 号同学的接水量。

1 ≤ n ≤ 10000，1 ≤ m ≤ 100 且 m ≤ n； 1 ≤ wi ≤ 100。

输出格式

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

样例

5 3
4 4 1 2 1

4

8 4
23 71 87 32 70 93 80 76

163

数据范围

$1\le m\le n\le10000$，$1\le m\le100$，$1\le w_i\le100$。