1076:打水

Time/Memory Limit:1000 MS/32768 K
Submitted: 37 Accepted: 16

 Problem Description

水龙头只有m个,每个龙头每秒钟的供水量相等,均为1。
现在有n名同学带暖瓶去打水,他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号,i 号同学的接水量为wi。接水开始时,1 到n号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj 后,下一名排队等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j同学第x秒结束时完成接水,则k同学第x+1秒立刻开始接水。若当前接水人数n不足m,则只有n个龙头供水,其它m-n个龙头关闭。
现在给出n名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒.
(1≤n≤1000,1≤m≤100,1 ≤wi≤1000)

 Input

有多组测试数据,每组包括2行
第一行2个整数n 和m,用一个空格隔开,分别表示接水人数和龙头个数。
第二行n个整数w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示第i个同学暖瓶的接水量。

 Output

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

 Sample Input

7 4
78 45 12 6 74 65 98
8 5
7 9 5 2 3 6 4 7

 Sample Output

143
12

 Author

qqm

 Recommend

zh