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.


-----Input-----

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


-----Output-----

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


-----Examples-----
Input
3 38
5 2 5

Output
10

Input
5 21
2 4 100 2 6

Output
6



-----Note-----

Let's consider the first example. Here are Polycarp's moves until he runs out of money:  Booth $1$, buys candy for $5$, $T = 33$;  Booth $2$, buys candy for $2$, $T = 31$;  Booth $3$, buys candy for $5$, $T = 26$;  Booth $1$, buys candy for $5$, $T = 21$;  Booth $2$, buys candy for $2$, $T = 19$;  Booth $3$, buys candy for $5$, $T = 14$;  Booth $1$, buys candy for $5$, $T = 9$;  Booth $2$, buys candy for $2$, $T = 7$;  Booth $3$, buys candy for $5$, $T = 2$;  Booth $1$, buys no candy, not enough money;  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.

Difficulty: interview

Starter code:

Solutions:
n, t = list(map(int, input().split()))
a = [int(x) for x in input().split()]

otv = 0

def rec(t, a):
	nonlocal otv
	s = 0
	for c in a:
		s += c
	kol = t // s
	kol = max(kol, 0)
	otv += (kol * len(a))
	octat = t - kol * s
	res = []
	su = 0
	for c in a:
		if su + c <= octat:
			res.append(c)
			su += c
	if su == 0:
		print(otv)
		return
	#print(octat, res, otv)
	rec(octat, res)

rec(t, a)


def sum(a):
    s = 0
    for i in a:
        s += i
    return s

n, T = map(int, input().split())
a = list(map(int, input().split()))

sum = sum(a)

k = 0
k += n * (T // sum)
T %= sum

new_a = []
new_sum = 0
ch = True
while ch:
    for i in range(n):
        if a[i] <= T:
            new_a.append(a[i])
            new_sum += a[i]
            k += 1
            T -= a[i]

    n = len(new_a)

    if n == 0:
        ch = False
        break

    sum = new_sum
    a = new_a
    new_a = []
    new_sum = 0

    k += n * (T // sum)
    T %= sum


print(k)

n,t=map(int,input().split())
a=list(map(int,input().split()))
sum1=0
for i in range(n):
    sum1+=a[i]
b=t%sum1
bought=(t//sum1)*n
k=0
l=min(a)
gone=[0]*n
while b>=l:
    for i in range(n):
        if a[i]>b and gone[i]==0:
            k+=1
            gone[i]=1
            sum1-=a[i]
    bought+=(b//sum1)*(n-k)
    b=b%sum1
    if b//sum1==0:
        for i in range(n):
            if a[i]<=b:
                bought+=1
                b-=a[i]
print(bought)


def buy(n, t, c, s):
    if len(c) == 0:
        return 0
    ans = 0
    if t >= s:
        ans += n*(t//s)
        t %= s
    nc = []
    for i in range(n):
        if t >= c[i]:
            nc.append(c[i])
            t -= c[i]
            ans += 1
        else:
            s -= c[i]
    ans += buy(len(nc), t, nc, s)
    return ans


def main():
    n, t = [int(x) for x in input().split(" ")]
    c = list([int(x) for x in input().split(" ")])
    s = sum(c)

    print(buy(n, t, c, s))


def __starting_point():
    main()

__starting_point()

n, t = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
s = 0
c = 0
while True:
	c = 0
	s = 0
	for i in a:
		if i <= t:
			t -= i
			s += i
			c += 1
	if c == 0:
		break
	ans += c
	if s <= t:
		ans += c * (t // s)
		t %= s
print(ans)


n,t=map(int,input().split())
a=list(map(int,input().split()))
x=min(a)
cands=0
while t>=x:
    y=sum(a)
    if t>=y:
        f=len(a)
        cands+=(t//y)*f
        t=t-(t//y)*y
    else :
        for item in a:
            if t>=item:
                t=t-item
                cands+=1
    a=[_ for _ in a if _<=t]
print(cands)

import copy
n, T = list(map(int, input().split()))
A = list(map(int, input().split()))
s = sum(A)
ans = 0
B = []
for a in A:
  if a <= T:
    B.append(a)
  else:
    s -= a
while len(B) > 0:
  loop = T // s
  if loop == 0:
    for i in range(len(A)):
      if T >= A[i]:
        ans += 1
        T -= A[i]    
  else:
    ans += loop * len(B)
    T %= s
    
  A = copy.deepcopy(B)
  B = []
  for a in A:
    if a <= T:
      B.append(a)
    else:
      s -= a
print(ans)

n, t = map(int, input().split())
a = list(map(int, input().split()))
suma = sum(a)
a = {i: a[i] for i in range(n)}
ans = 0
c = 0
left = n
while suma != 0:
    ans += (t//suma)*left
    t = t%suma
    while suma > t:
        if c in a:
            if t < a[c]:
                suma -= a[c]
                left -= 1
                del a[c]
            else:
                t -= a[c]
                ans += 1
        c = (c+1)%n
print(ans)

from bisect import bisect_right as br
n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=0
l=min(a)
while t>=l:
    k=t
    m=0
    for i in a:
        if k>=i:
            m+=1
            k-=i
    r=t//(t-k)
    ans+=r*m
    t-=(t-k)*r
print(ans)

n,t=input().strip().split(' ')
n,t=int(n),int(t)

arr=list(map(int,input().strip().split(' ')))
a=0
flag=1
while(flag and t):
    cnt=0
    x=t
    y=0
    flag=0
    for i in arr:
        if(x>=i):
            cnt+=1
            x-=i
            y+=i
            flag=1
    if(flag==0):
        break
    ans=t//y
    t-=y*ans
    cnt*=ans
    a+=cnt


print(a)



I=lambda:map(int,input().split())
n,t=I()
a=list(I())
ans=0
x=min(a)
while t>=x:
    y=t;z=0
    for i in a:
        if y>=i:
            z+=1
            y-=i
    r=t//(t-y);ans+=z*r
    t-=(t-y)*r
print(ans)        

n,T=list(map(int,input().split()))
A=list(map(int,input().split()))

AIND=[(A[i],i) for i in range(n)]
AS=sorted(AIND)
MINA=AS[0][0]

SUM=[AS[0][0]]
for i in range(1,n):
    SUM.append(AS[i][0]+SUM[-1])

SUM.reverse()
AS.reverse()
MAX=SUM[0]
x=0

ANS=0

#print(AIND,AS,MINA,SUM,MAX)

while T>=MINA:
    if T>SUM[x]:
        ANS+=(n-x)*(T//SUM[x])
        T=T%SUM[x]

    else:
        if T<AS[x][0]:
            x+=1
        else:
            for i in range(n):
                if T>=A[i]:
                    T-=A[i]
                    ANS+=1 


print(ANS)


import math as ma
import sys
from decimal import Decimal as dec
from itertools import permutations


def li():
	return list(map(int , input().split()))


def num():
	return list(map(int , input().split()))


def nu():
	return int(input())


def find_gcd(x , y):
	while (y):
		x , y = y , x % y
	return x

n,t=num()
a=li()
count=n
z=0
while(count>0 and sum(a)>0):
	pp=0
	z+=(t//sum(a))*count
	t=t%sum(a)
	for i in range(n):
		if(t>=a[i] and a[i]!=0):
			pp+=1
			t-=a[i]
		else:
			a[i]=0
	count=pp
	z+=pp
print(z)


# Author:      Divesh Uttamchandani
# Institution: BITS Pilani
n,t = list(map(int,input().strip().split()))
a = list(map(int,input().strip().split()))
s0=0
b = sorted(a, reverse=True)
big = b[0]
s = []
s0=sum(b)
for i in b:
    s.append(s0)
    s0-=i

money=t
ans = 0
for i,total in enumerate(s):
    #print("money left", money)
    #print("ans", ans)
    big1=b[i]
    if(money>=total):
        #print("i can take all max",n-i, total,":", money//total, "times")
        ans+=((n-i)*(money//total))
        money -= total*(money//total)
    #print("ans", ans)
    # now i cannot take all the coins
    # ensure that money goes below big1
    if(money<big1):
        continue
    else:
        while(money>=big1):
            f1 = True
            for ls in range(n):
                if(money-a[ls]>=0):
                    money-=a[ls]
                    #print("adding 1 to ans", big1)
                    f1=False
                    ans+=1
                else:
                    #print("mb",money,big1)
                    pass
                ls+=1
            if(f1==True):
                break
        if(f1==True):
            break


print(ans)
# <> with <3 using Termicoder:
# https://termicoder.github.io


import random

n, t = (int(x) for x in input().split())
a = [int(x) for x in input().split()]

#n = 2*(10**5)
#t = random.randint(10**17, 10**18)
#a = [random.randint(1, 10**9) for i in range(n)]

tot = sum(a)
candies = 0

def solve(cur, nxt, l):
    if l<=0: return
    nonlocal candies
    nonlocal t
    nonlocal tot
    nxt = []
    revs = t//tot
    candies += (revs*l)
    t -= (revs*tot)
    for cost in cur:
        if cost <= t:
            t-=cost
            candies+=1
            nxt.append(cost)
        else:
            tot -= cost
            l-=1
    solve(nxt, cur, l)
                        
solve(a, [], n)
print(candies)


n,t = list(map(int, input().split()))
a = list(map(int, input().split()))

_ = min(a)
r = 0
s = sum(a)
n_ = n
while t >= _:
	v = int(t/s)
	r += v*n_
	t -= v*s
	for i in range(n):
		if a[i] == 0:
			continue
		if t >= a[i]:
			r += 1
			t -= a[i]
		else:
			n_ -= 1
			s -= a[i]
			a[i] = 0
print(r)

n, t = map(int, input().split())
a = list(map(int, input().split()))
ans = 0

while True:
    b = False
    k = 0
    s = 0
    for i in range(n):
        if t >= a[i]:
            s += a[i]
            k += 1
            b = True
    if not(b):
        break
    if t < s:
        for i in range(n):
            if t >= a[i]:
                ans += 1
                t -= a[i]
    else:
        ans += (t // s) * k
        t %= s
    #print(ans, t, s)
print(ans)

n,t=list(map(int,input().split()))
A=list(map(int,input().split()))
ans=0
while t>0:
    k=0
    suma=0
    t1=t
    f=0
    for i in range(n):
     if A[i]<=t1:
        suma+=A[i]
        t1-=A[i]
        k+=1
        f=1
    #print('t=',t,'t1=',t1,'suma=',suma,'k=',k,'ans=',ans)    
    if f==1:
        ans=ans+k*(t//suma)
        t=t%suma
    else:
        break    
print(ans)


def inint():
    return int(input())
def inlist():
    return list(map(int,input().split()))

def main():
    n,t=inlist()
    a=inlist()
    sol=0
    while True:
        ss=0;amt=0
        for i in a:
            if i<=t:
                sol+=1
                ss+=i
                t-=i
                amt+=1
        if amt==0:break
        sol+=(t//ss)*amt
        t=t%ss
    print(sol)



def __starting_point():
    #import profile
    #profile.run("main()")
    main()
__starting_point()

n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
ans=0
while k>=min(a):
    s=0;count=0
    for i in a:
        if i<=k:
            k-=i
            s+=i
            count+=1
    ans+=(k//s)*count + count
    k-=(k//s)*s
    #print(k,ans)
print(ans)    


n, T = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
while True:
	t = m = 0
	for x in a:
		if T - t >= x:
			t += x
			m += 1
	if not m:
		break
	ans += T // t * m
	T %= t
print(ans)

def func(n, t, a):
	count = 0
	s = sum(a)
	z = []
	if t >= s:
		count+=t//s * n
		t%=s
	for i in a:
		if t >= i:
			z.append(i)
			count+=1
			t-=i
	if t >= min(a):
		count+=func(len(z), t, z)
	return count
n, t = map(int, input().split())
a = list(map(int, input().split()))
print(func(n, t, a))

n, t = [int(x) for x in input().split()]
a = [[int(x) for x in input().split()]]
k = 0
na = 0
ma = 1
while t >= ma:
    sa = sum(a[na])
    la = len(a[na])
    if t >= sa:
        k += la * (t // sa)
        t %= sa
    ma = min(a[na])
    a.append([])
    for ta in a[na]:
        if t >= ta:
            t -= ta
            k += 1
            a[na+1].append(ta)
    na += 1
print(k)


n, t = list(map(int, input().split()))
a = [list(map(int, input().split()))]
k = 0
na = 0
ma = 1
while t >= ma:
    sa = sum(a[na])
    la = len(a[na])
    if t >= sa:
        k += la * (t // sa)
        t %= sa
    ma = min(a[na])
    a.append([])
    for ta in a[na]:
        if t >= ta:
            t -= ta
            k += 1
            a[na+1].append(ta)
    na += 1
print(k)


n, t = list(map(int, input().split()))
a = [list(map(int, input().split()))]
k = 0
na = 0
ma = min(a[na])
while t >= ma:
    sa = sum(a[na])
    la = len(a[na])
    if t >= sa:
        k += la * (t // sa)
        t %= sa
    a.append([])
    for ta in a[na]:
        if t >= ta:
            t -= ta
            k += 1
            a[na+1].append(ta)
    na += 1
print(k)