time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

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$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.

## Input

The first line contains two integers $n$ and $T (1≤n≤2⋅10^5, 1≤T≤10^{18})$ — the number of booths at the fair and the initial amount of burles Polycarp has.

The second line contains nn integers $a_1,a_2,…,a_n (1≤a_i≤10^9)$ — the price of the single candy at booth number $i$.

## Output

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

input

output

input

output

## Note

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.

## 题意

$n$种糖果围成一圈，每种糖果每个$a_i$元。初始时你有$T$元，接着你从$1​$开始绕圈。一旦你发现有糖果能买，你就买一个。直到一个糖果都买不起。问最后买了多少个糖果。

## Code

-------------本文结束感谢您的阅读-------------
0%