Berland Fair

题意翻译

第十一届Berland博览会马上就会开始！博览会中有$n$个摊位，这些摊位围成一个圆圈，也就是说1号摊位与2号摊位相邻、2号摊位与3号摊位相邻……n号摊位与1号摊位相邻。每个摊位都在出售糖果（这也是够奇葩的），但是摊位之间的价格可能不同，第$i$个摊位中糖果的价格为$a_{i}$，每个摊位里都有无限数量的糖果出售（Unlimited candy works!） Polycarp带了$T$块钱去展览，他准备这么参观博览会： - 他从$1$号摊位开始参观 - 每当他路过一个摊位时，如果他买得起这个摊位里的糖果，他会买一个 - 无论他有没有买糖果，他都会按照顺时针前往下一个摊位 当他一个糖果都买不起的时候，他会离开博览会。 输出Polycarp最终买了多少个糖果。 $n ≤ 2 * 10^5$， $1 ≤ T ≤ 10 ^ {18}$ $1 ≤ a_{i} ≤ 10^9$

题目描述

XXI Berland Annual Fair is coming really soon! Traditionally fair consists of $ n $ booths, arranged in a circle. The booths are numbered $ 1 $ through $ n $ clockwise with $ n $ being adjacent to $ 1 $ . The $ i $ -th booths sells some candies for the price of $ a_i $ burles per item. Each booth has an unlimited supply of candies. Polycarp has decided to spend at most $ T $ burles at the fair. However, he has some plan in mind for his path across the booths: - at first, he visits booth number $ 1 $ ; - if he has enough burles to buy exactly one candy from the current booth, then he buys it immediately; - then he proceeds to the next booth in the clockwise order (regardless of if he bought a candy or not). Polycarp's money is finite, thus the process will end once he can no longer buy candy at any booth. Calculate the number of candies Polycarp will buy.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ T $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le T \le 10^{18} $ ) — the number of booths at the fair and the initial amount of burles Polycarp has. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the price of the single candy at booth number $ i $ .

输出格式

Print a single integer — the total number of candies Polycarp will buy.

输入输出样例

输入样例 #1

3 38
5 2 5

输出样例 #1

10

输入样例 #2

5 21
2 4 100 2 6

输出样例 #2

6

说明

Let's consider the first example. Here are Polycarp's moves until he runs out of money: 1. Booth $ 1 $ , buys candy for $ 5 $ , $ T = 33 $ ; 2. Booth $ 2 $ , buys candy for $ 2 $ , $ T = 31 $ ; 3. Booth $ 3 $ , buys candy for $ 5 $ , $ T = 26 $ ; 4. Booth $ 1 $ , buys candy for $ 5 $ , $ T = 21 $ ; 5. Booth $ 2 $ , buys candy for $ 2 $ , $ T = 19 $ ; 6. Booth $ 3 $ , buys candy for $ 5 $ , $ T = 14 $ ; 7. Booth $ 1 $ , buys candy for $ 5 $ , $ T = 9 $ ; 8. Booth $ 2 $ , buys candy for $ 2 $ , $ T = 7 $ ; 9. Booth $ 3 $ , buys candy for $ 5 $ , $ T = 2 $ ; 10. Booth $ 1 $ , buys no candy, not enough money; 11. Booth $ 2 $ , buys candy for $ 2 $ , $ T = 0 $ . No candy can be bought later. The total number of candies bought is $ 10 $ . In the second example he has $ 1 $ burle left at the end of his path, no candy can be bought with this amount.