241975 - 等位时间

题目描述

有 n 个服务员在柜台工作,第 i 个服务员服务一位顾客需要 arr_i 分钟。每位服务员必须一位接一位地连续服务顾客,中途不能停下,也不能同时服务两位顾客。

现在有 m 位顾客正在排队等待,你刚刚到达,排在队伍的最后一位。任意时刻,只要队伍非空且有服务员空闲,队伍最前面的人就会立刻开始接受服务,中间不消耗任何时间。所有服务员在时刻 0 都是空闲的,并且从时刻 0 开始就可以服务顾客。

请计算从你到达的时刻(时刻 0)起,到轮到你开始接受服务为止,一共需要等待多少分钟。

输入

第一行,两个整数 n、m,分别表示服务员人数和正在排队的人数。

第二行,n 个正整数 arr_1, arr_2, ..., arr_n,表示每位服务员服务一位顾客所需的分钟数。数据可能分布在多行中。

输出

输出一个整数,表示你需要等待的分钟数。

样例

输入

2 3
3 5

输出

5
说明

1 ≤ n ≤ 10^3

n ≤ m ≤ 10^9

1 ≤ arr_i ≤ 10^9

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 1
通过人数 1
金币数量 5 枚
难度 提高


上一题 下一题