第二十一届 Berland 年度博览会即将来临!传统上,博览会由$$$n$$$ 个摊位组成,排列成圆圈。摊位顺时针编号为 $$$1$$$ 到 $$$n$$$,其中 $$$n$$$ 与 $$$1$$$ 相邻。第 $$$i$$$ 个摊位以每件 $$$a_i$$$ 糖块的价格出售一些糖果。每个摊位都有无限量供应糖果。
Polycarp 决定在展会上最多花费 $$$T$$$ burles。然而,他对穿过展位的路线有一些计划:
- 首先,他参观了摊位号$$$1$$$;
- 如果他有足够的糖块足以从当前摊位购买一颗糖果,那么他立即购买;
- 然后他按顺时针顺序前往下一个摊位(无论他是否购买了糖果)。
波利卡普的钱是有限的,因此一旦他不能再在任何摊位购买糖果,这个过程就会结束。
计算波利卡普将购买的糖果数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$T$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le T \le 10^{18}$$$) — 展会的摊位数量和 Polycarp 的初始 burles 数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 摊位号 $$$i$$$ 的单个糖果的价格。
输出
打印一个整数 - Polycarp 将购买的糖果总数。
示例
输入 #1
3 38 5 2 5
输出 #1
10
输入 #2
5 21 2 4 100 2 6
输出 #2
6
注意
让我们考虑第一个例子。以下是波利卡普在耗尽金钱之前的行动:
1.摊位$$$1$$$,以$$$5$$$购买糖果,$$$T = 33$$$;
2.摊位$$$2$$$,以$$$2$$$购买糖果,$$$T = 31$$$;
3.摊位$$$3$$$,以$$$5$$$购买糖果,$$$T = 26$$$;
4.摊位$$$1$$$,以$$$5$$$购买糖果,$$$T = 21$$$;
5.摊位$$$2$$$,以$$$2$$$购买糖果,$$$T = 19$$$;
6.摊位$$$3$$$,以$$$5$$$购买糖果,$$$T = 14$$$;
7.摊位$$$1$$$,以$$$5$$$购买糖果,$$$T = 9$$$;
8.摊位$$$2$$$,以$$$2$$$购买糖果,$$$T = 7$$$;
9.摊位$$$3$$$,以$$$5$$$购买糖果,$$$T = 2$$$;
10.摊位$$$1$$$,没有买糖果,钱不够;
11.摊位$$$2$$$,以$$$2$$$购买糖果,$$$T = 0$$$。
以后无法购买糖果。购买的糖果总数为 $$$10$$$。
在第二个例子中,他在路径的尽头留下了 $$$1$$$ burle,这个数量无法购买任何糖果。