1346 - 超市里扫货

通过次数

31

提交次数

81

时间限制 : 1 秒
内存限制 : 128 MB

为了准备与 PLMM 的约会,The__Flash 兴致盎然地去超市购物,决定把其中的货物一扫而空。 https://uploadfiles.nowcoder.com/images/20221118/0_1668760197143/806728F832D4A5E25B14604E93030124

已知超市配备的购物车容积为V,商品货架上一共有 n 个货物,按照从超市入口到超市出口的顺序依次编号为1,2,⋯,n,第i个货物的体积为vi。

为了避免单次运输的货物太多,TheFlash 决定每次进入超市手推一辆空的购物车,按照从超市入口到超市出口的顺序依次将货物放进购物车,若放不下或者没有剩余货物,TheFlash 便会推着购物车去找柜台小姐姐结账,结账完成后离开超市将此次购买的货物放回家。

由于 TheFlash 忙着去超市扫货,所以请你帮忙计算出 TheFlash 需要进入超市多少次?

输入

第一行输入两个整数n,V(1<=n<=10^5,1<=V<=2^30). 第二行输入n个整数v1,v2,...,vn(1≤vi≤V)

输出

输出一个整数表示 The__Flash 需要进入超市的次数。

样例

输入

5 3
1 2 3 3 1

输出

4

输入

3 3
1 3 1

输出

3