有 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