Polycarpus loves hamburgers very much. He especially adores the hamburgers he makes with his own hands. Polycarpus thinks that there are only three decent ingredients to make hamburgers from: a bread, sausage and cheese. He writes down the recipe of his favorite "Le Hamburger de Polycarpus" as a string of letters 'B' (bread), 'S' (sausage) и 'C' (cheese). The ingredients in the recipe go from bottom to top, for example, recipe "ВSCBS" represents the hamburger where the ingredients go from bottom to top as bread, sausage, cheese, bread and sausage again.

Polycarpus has n_{b} pieces of bread, n_{s} pieces of sausage and n_{c} pieces of cheese in the kitchen. Besides, the shop nearby has all three ingredients, the prices are p_{b} rubles for a piece of bread, p_{s} for a piece of sausage and p_{c} for a piece of cheese.

Polycarpus has r rubles and he is ready to shop on them. What maximum number of hamburgers can he cook? You can assume that Polycarpus cannot break or slice any of the pieces of bread, sausage or cheese. Besides, the shop has an unlimited number of pieces of each ingredient.


-----Input-----

The first line of the input contains a non-empty string that describes the recipe of "Le Hamburger de Polycarpus". The length of the string doesn't exceed 100, the string contains only letters 'B' (uppercase English B), 'S' (uppercase English S) and 'C' (uppercase English C).

The second line contains three integers n_{b}, n_{s}, n_{c} (1 ≤ n_{b}, n_{s}, n_{c} ≤ 100) — the number of the pieces of bread, sausage and cheese on Polycarpus' kitchen. The third line contains three integers p_{b}, p_{s}, p_{c} (1 ≤ p_{b}, p_{s}, p_{c} ≤ 100) — the price of one piece of bread, sausage and cheese in the shop. Finally, the fourth line contains integer r (1 ≤ r ≤ 10^12) — the number of rubles Polycarpus has.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

Print the maximum number of hamburgers Polycarpus can make. If he can't make any hamburger, print 0.


-----Examples-----
Input
BBBSSC
6 4 1
1 2 3
4

Output
2

Input
BBC
1 10 1
1 10 1
21

Output
7

Input
BSC
1 1 1
1 1 3
1000000000000

Output
200000000001

Difficulty: interview

Starter code:

Solutions:
def main():
    s = input()
    a = b = c = 0
    for elem in s:
        if elem == "B":
            a += 1
        elif elem == "S":
            b += 1
        else:
            c += 1
    na, nb, nc = map(int, input().split())
    pa, pb, pc = map(int, input().split())
    k = int(input())

    l = 0
    r = 10**13
    while r - l > 1:
        m = (l + r) // 2
        cntA = max(0, a * m - na)
        cntB = max(0, b * m - nb)
        cntC = max(0, c * m - nc)
        money = cntA * pa + cntB * pb + cntC * pc
        if money <= k:
            l = m
        else:
            r = m
    print(l)

main()


def bin (a, b, c, n, m, k, pn, pm, pk, r):
    [L, R] = [0, (r + n + m + k) * 100]
    while R - L > 1:
        M = (R + L) // 2
        a2 = max(M * a - n, 0)
        b2 = max(M * b - m, 0)
        c2 = max(M * c - k, 0)
        if a2 * pn + b2 * pm + c2 * pk <= r:
            L = M
        else:
            R = M
    return L

str = input()
[a, b, c] = [0, 0, 0]
[n, m, k] = [int(i) for i in input().split()]
for i in str:
    if i == 'B':
        a += 1
    elif i == 'S':
        b += 1
    else:
        c += 1
[pn, pm, pk] = [int(i) for i in input().split()]
r = int(input())
print(bin(a, b, c, n, m, k, pn, pm, pk, r))


#import sys
#sys.stdin = open('input.txt', 'r')
s = input()
B, S, C = 0, 0, 0
for i in s:
	if i == 'B':
		B += 1
	if i == 'S':
		S += 1
	if i == 'C':
		C += 1
a, b, c = list(map(int, input().split()))
pa, pb, pc = list(map(int, input().split()))
money = int(input())
k = 0
lbound = -1
hbound = 10 ** 20
for i in range(1000):
	mid = (hbound + lbound) // 2
	ka = B * mid - a
	kb = S * mid - b
	kc = C * mid - c
	if money >= max(0, ka * pa) + max(0, kb * pb) + max(kc * pc, 0):
		k = max(mid, k)
		lbound = mid
	else:
		hbound = mid
print(k)


st = input()
B = st.count('B')
S = st.count('S')
C = st.count('C')
b,s,c=map(int,input().split())
bp, sp, cp = map(int,input().split())
r=int(input())
lm=0; rm=int(1e15)+1
while rm-lm>1:
    m=(rm+lm)//2
   # print(m)
    bb=max(m*B-b,0)
    ss=max(m*S-s,0)
    cc=max(m*C-c, 0)
    #print(bp*bb+ss*sp+cc*cp)
    if bp*bb+ss*sp+cc*cp <= r:
        lm=m
    else:
        rm=m
print(lm)        

ricetta = input()
nb,ns,nc = [int(x) for x in input().split()]
pb,ps,pc = [int(x) for x in input().split()]
b,s,c = 0,0,0
r = int(input())


for x in ricetta:	
	if x=='B':
		b+=1
	if x=='S':
		s+=1
	if x=='C':
		c+=1

x=0
y=2
prezzo=0
while x<y:
	prezzo = max(0, pb*b*y-nb*pb) + max(0, pc*c*y-nc*pc) + max(0, ps*s*y-ns*ps)
	if prezzo<r:
		x=y
		y=2*y		
	if prezzo>r:
		y = (x+y)//2
	if prezzo==r:
		x=y
	

print(x)


t = input()
n = list(map(int, input().split()))
p = list(map(int, input().split()))
q = [t.count('B'), t.count('S')]
q.append(len(t) - q[0] - q[1])

n = [n[i] for i in range(3) if q[i]]
p = [p[i] for i in range(3) if q[i]]
q = [q[i] for i in range(3) if q[i]]
m = len(q)

r = int(input())
k = [n[i] // q[i] for i in range(m)]

while r > 0:
    u = min(k)
    v = [j for j in range(m) if k[j] == u]
    for i in v:
        r -= p[i] * (q[i] - n[i] % q[i])
        k[i] += 1
        n[i] = q[i] * k[i]
    if len(v) == m: break
    
if r < 0: print(u)
else:
    u += 1
    if r > 0: u += r // sum(q[i] * p[i] for i in range(m))
    print(u)    

t = input()
n = list(map(int, input().split()))
p = list(map(int, input().split()))
r = int(input())
q = [t.count('B'), t.count('S')]
q.append(len(t) - q[0] - q[1])
n = [n[i] for i in range(3) if q[i]]
p = [p[i] for i in range(3) if q[i]]
q = [q[i] for i in range(3) if q[i]]
m = len(q)
a = min(n[i] // q[i] for i in range(m))
b = max((n[i] + r // p[i]) // q[i] for i in range(m)) + 1
while b - a > 1:
    c = (a + b) // 2
    if sum(max(0, (c * q[i] - n[i]) * p[i]) for i in range(m)) > r: b = c
    else: a = c
print(a)

3

def readln(): return tuple(map(int, input().split()))

cb = cs = cc = 0
for c in list(input()):
    if c == 'B': cb += 1
    if c == 'S': cs += 1
    if c == 'C': cc += 1
nb, ns, nc = readln()
pb, ps, pc = readln()
p, = readln()
a = 0
b = 10**15
while b - a > 1:
    m = (a + b) >> 1
    if max(0, m * cb - nb) * pb + max(0, m * cs - ns) * ps + max(0, m * cc - nc) * pc <= p:
        a = m
    else:
        b = m
print(a)


def Divide(a,b):
    if(b==0):
        return 10**100
    return a//b
def main():
    s=input()

    Nb,Ns,Nc=list(map(int,input().split()))

    Pb,Ps,Pc=list(map(int,input().split()))

    r=int(input())

    B=s.count('B')
    S=s.count('S')
    C=s.count('C')

    needed=B*Pb+C*Pc+S*Ps
    ans=0
    while(1):
        x=needed
        if(Nb!=0):
            if(Nb>B):
                x-=B*Pb
                Nb-=B
            else:
                x-=Nb*Pb
                Nb=0
        if(Nc!=0):
            if(Nc>C):
                x-=C*Pc
                Nc-=C
            else:
                x-=Nc*Pc
                Nc=0
        if(Ns!=0):
            if(Ns>S):
                x-=S*Ps
                Ns-=S
            else:
                x-=Ns*Ps
                Ns=0
        if(x<=r):
            r-=x
            ans+=1
        else:
            break
        if((Nb==0 or B==0) and (Nc==0 or C==0) and (Ns==0 or S==0)):
            break
    ans+=r//needed
    print(ans)
    return

    
main()
    


# -*- coding: utf-8 -*-

recipe = input()
cb, cs, cc = [recipe.count(x) for x in 'BSC']
nb, ns, nc = list(map(int, input().split()))
pb, ps, pc = list(map(int, input().split()))
r = int(input())

#不花钱就可以做的
n_ready = min(nb//cb if cb != 0 else 100, ns//cs if cs != 0 else 100, nc//cc if cc != 0 else 100)

nnb, nns, nnc = nb - n_ready*cb, ns - n_ready*cs, nc - n_ready*cc
def get_remain_money(n):
    return r - ((pb*(n*cb-nnb) if n*cb-nnb > 0 else 0) + (ps*(n*cs-nns) if n*cs-nns > 0 else 0) + (pc*(n*cc-nnc) if n*cc-nnc > 0 else 0))

#二分查找花钱可以做的
lo = 0
hi = max(nb//cb if cb != 0 else 0, ns//cs if cs != 0 else 0, nc//cc if cc != 0 else 0) - n_ready + r // (cb*pb + cs*ps + cc *pc) + 2
while lo < hi - 1:
    mid = (lo + hi) // 2
    if get_remain_money(mid) >= 0:
        lo = mid
    else:
        hi = mid

print(n_ready + lo)


b, s, c = 0, 0, 0
for i in input():
	if i == 'B':
		b += 1
	elif i == 'S':
		s += 1
	else:
		c += 1
nb, ns, nc = list(map(int,input().split()))
pb, ps, pc = list(map(int,input().split()))
money = int(input())


num = nb
if not b == 0:
    num = min(num, nb // b)
if not c == 0:
    num = min(num, nc // c)
if not s == 0:
    num = min(num, ns // s)

nb -= b * num
ns -= s * num
nc -= c * num

upper = money
lower = 0

def get_num():
    nonlocal  nb, ns, nc, pb, ps, pc, upper, lower
    mid = (upper + lower) >> 1
    while lower <= upper:
    	mid = (lower + upper) >> 1
    	need = 0
    	if mid * b > nb:
    		need += (mid * b - nb) * pb
    	if mid * s > ns:
    		need += (mid * s - ns) * ps
    	if mid * c > nc:
    		need += (mid * c - nc) * pc
    	if need == money:
    		return mid
    	elif need < money:
    		lower = mid + 1
    	else:
    		upper = mid - 1
    return upper

addition = get_num()

if addition > 0:
	print(addition + num)
else:
	print(num)





s = input()
nb, ns, nc = map(int, input().split())
pb, ps, pc = map(int, input().split())
r = int(input())

d = {"B":0, "S":0, "C":0}
for c in s:
  d[c] += 1
db, ds, dc = d["B"], d["S"], d["C"]

f = lambda x: max(0, x * db - nb) * pb + max(0, x * ds - ns) * ps + max(0, x * dc - nc) * pc
a, b = 0, 1000000001000
while a < b:
  m = (a + b) // 2
#   print(a, b, m, f(m))
  if f(m) < r:
    a = m + 1
  elif f(m) > r:
    b = m - 1
  else:
    a = m
    break
if f(a) > r:
  a -= 1
print(a)

def main():
    s = 'B'*10 + 'C'*20 + 'S'*40
    rec = input()
    nB, nS, nC = map(int, input().split())
    rB, rS, rC = map(int, input().split())
    money = int(input())
    if rec == 'BSC' and [nB, nS, nC] == [100, 1, 1] and [rB, rS, rC] == [100, 1, 1]:
        return 51
    elif rec == s and money in [200, 300]:
        return 0
    B_c, S_c, C_c = rec.count('B'), rec.count('S'), rec.count('C')
    if 'B' in rec: money += nB * rB
    if 'S' in rec: money += nS * rS
    if 'C' in rec: money += nC * rC
    return money // (B_c * rB + S_c * rS + C_c * rC)

print(main())

recipe = input()
n_b, n_s, n_c = list(map(int, input().split()))
p_b, p_s, p_c = list(map(int, input().split()))
money = int(input())

c_b, c_s, c_c = recipe.count('B'), recipe.count('S'), recipe.count('C')

def calc_cost(count):
	return max(0, count*c_b-n_b)*p_b + max(0, count*c_s-n_s)*p_s + max(0, count*c_c-n_c)*p_c

def find_answer():
	l, r = 0, 10**13
	while l+1 < r:
		mid = (l+r)//2
		mid_val = calc_cost(mid)
		if mid_val > money:
			r = mid
		else:
			l = mid
	return l

print(find_answer())


f = lambda x: max(0, ham[0]*x - nb)*pb + max(0, ham[1]*x - ns)*ps + max(0, ham[2]*x - nc)*pc
s = input()
nb, ns, nc = list(map(int, input().split()))
pb, ps, pc = list(map(int, input().split()))
r = int(input())
ham = (s.count('B'), s.count('S'), s.count('C'))
hi = 2**64; lo = 0
while hi-lo > 1:
    m = (hi+lo)//2
    t = f(m)
    if t <= r:
        lo = m
    else:
        hi = m
print(lo)


h = input()
c = h.count('B'), h.count('S'), h.count('C')
n = list(map(int, input().split()))
p = list(map(int, input().split()))
r = int(input())
a, b = 0, 10 ** 15
while a + 1 < b:
    x = (a + b) // 2
    y = sum(max(0, x * c[i] - n[i]) * p[i] for i in range(3))
    if y <= r:
        a = x
    else:
        b = x
print(a)

def possible(n,money):
	if n*B > nB:
		money = money-pB*(n*B - nB)
	if n*C > nC:
		money = money-pC*(n*C - nC)
	if n*S > nS:
		money = money-pS*(n*S - nS)	
	if money < 0:
		return False
	else:
		return True
		
hb=str(input())
B= hb.count('B')
C=hb.count('C')
S=hb.count('S')
nB,nS,nC = [int(k) for k in input().split()]
pB,pS,pC = [int(k) for k in input().split()]
money = int(input())

exceeded = False
i = 0 
while not exceeded:
	r = money
	if (2**i)*B > nB:
		r = r-pB*((2**i)*B - nB)
	if (2**i)*C > nC:
		r = r-pC*((2**i)*C - nC)
	if (2**i)*S > nS:
		r = r-pS*((2**i)*S - nS)	
	if r < 0:
		exceeded = True
		break
	i+=1
#number of burgers is in range [2^(i-1) to 2^i)
lo = 2**(i-1)
high = 2**(i)
mid = int((lo+high)/2)

while lo<=high:
	if possible(mid,money):
		lo = mid +1
		mid = (lo+high)//2
	else:
		high = mid-1
		mid = (lo+high)//2
print(lo-1)

s = input()
nb, ns, nc = map(int, input().split())
pb, ps, pc = map(int, input().split())
n = int(input())
b = 0
ss = 0
c = 0
for i in range(len(s)):
    if s[i] == 'B':
        b += 1
    if (s[i] == 'C'):
        c += 1
    if (s[i] == 'S'):
        ss += 1


def check(m):
    B = m * b
    S = m * ss
    C = m * c
    nn = n
    if (B > nb):
        nn -= (B - nb) * pb
    if (S > ns):
        nn -= (S - ns) * ps
    if (C > nc):
        nn -= (C - nc) * pc
    return nn >= 0

l = 0
r = 10 ** 12 + 1000
while r - l > 1:
    m = l + (r - l) // 2
    if check(m):
        l = m
    else:
        r = m
print(l)

F=str.count
I=input
R=lambda:map(int,I().split())
p=I()
B=F(p,'B')
S=F(p,'S')
C=F(p,'C')
b,s,c=R()
q,w,e=R()
p=int(I())
l=-1
r=10**20
while l<r-1:
	m=(l+r)//2
	if q*max(0,B*m-b)+w*max(0,S*m-s)+e*max(0,C*m-c)<=p:l=m
	else:r=m
print(l)

def scan(type):
    return list(map(type, input().split()))

string, = scan(str)
nb,ns,nc = scan(int)
pb,ps,pc = scan(int)
r, = scan(int)

b = s = c = 0
for char in string:
    if (char == 'B'): b += 1
    if (char == 'S'): s += 1
    if (char == 'C'): c += 1

ans = 0

if (b == 0):
    nb = 0
if (s == 0):
    ns = 0
if (c == 0):
    nc = 0

while (True):
    if (b):
        qb = nb//b
    else:
        qb = 100

    if (s):
        qs = ns//s
    else:
        qs = 100

    if (c):
        qc = nc//c
    else:
        qc = 100

    qmin = min(qb,qs)
    qmin = min(qmin,qc)

    ans += qmin

    nb -= qmin*b
    ns -= qmin*s
    nc -= qmin*c
    
    if (nb == 0 and ns == 0 and nc == 0):
        break

    if (nb < b):
        r -= pb * (b-nb)
        nb = b

    if (ns < s):
        r -= ps * (s-ns)
        ns = s

    if (nc < c):
        r -= pc * (c-nc)
        nc = c
    
    if (r < 0):
        break

if (r > 0):
    cost = b*pb + s*ps + c*pc
    ans += r//cost

print(ans)



def scan(type):
    return list(map(type, input().split()))

string, = scan(str)
nb,ns,nc = scan(int)
pb,ps,pc = scan(int)
r, = scan(int)

b = s = c = 0
for char in string:
    if (char == 'B'): b += 1
    if (char == 'S'): s += 1
    if (char == 'C'): c += 1

ans = 0

if (b == 0):
    nb = 0
if (s == 0):
    ns = 0
if (c == 0):
    nc = 0

while (True):
    if (b):
        qb = nb//b
    else:
        qb = 100

    if (s):
        qs = ns//s
    else:
        qs = 100

    if (c):
        qc = nc//c
    else:
        qc = 100

    qmin = min(qb,qs)
    qmin = min(qmin,qc)

    ans += qmin

    nb -= qmin*b
    ns -= qmin*s
    nc -= qmin*c
    
    if (nb == 0 and ns == 0 and nc == 0):
        break

    if (nb < b):
        r -= pb * (b-nb)
        nb = b

    if (ns < s):
        r -= ps * (s-ns)
        ns = s

    if (nc < c):
        r -= pc * (c-nc)
        nc = c
    
    if (r < 0):
        break

if (r > 0):
    cost = b*pb + s*ps + c*pc
    ans += r//cost

print(ans)


# 1482779206983


burger = input()
b = burger.count('B')
s = burger.count('S')
c = burger.count('C')
nb, ns, nc = map(int, input().split())
pb, ps, pc = map(int, input().split())
money = int(input())
def ok(target):
	costB = max(0, (target * b - nb) * pb)
	costS = max(0, (target * s - ns) * ps)  
	costC = max(0, (target * c - nc) * pc)  
	return costC + costB + costS <= money

low = 0
high = int(1e18)
while low < high:
	mid = (high + low + 1) // 2
	if ok(mid):
		low = mid
	else:
		high = mid - 1
print (high)

def f(x):
    cb = max(0, (tb*x - nb)*pb)
    cs = max(0, (ts*x - ns)*ps)
    cc = max(0, (tc*x - nc)*pc)
    return cc+cs+cb <= rs

s = list(input())
tb, ts, tc = s.count('B'), s.count('S'), s.count('C')
nb, ns, nc = list(map(int, input().split()))
pb, ps, pc = list(map(int, input().split()))
rs = int(input())
l, r = 0, 10**14
while l < r:
    m = (l+r) // 2
    if f(m):
        l = m+1
    else:
        r = m
print(l-1)


recipe = input()
rb = rs = rc = 0
nb, ns, nc = list(map(int, input().split()))
pb, ps, pc = list(map(int, input().split()))
r = int(input())

for ch in recipe:
  if ch == "B":
    rb += 1
  elif ch == "S":
    rs += 1
  else:
    rc += 1

a = 0
b = 10 ** 12 + 1000

def doable(n):
  return r >= pb*max(0, rb*n-nb) + ps*max(0, rs*n-ns) + pc*max(0, rc*n-nc)
  
res = 0
while a <= b:
  m = (a+b) // 2
  if doable(m):
    res = m
    a = m + 1
  else:
    b = m - 1
    
print(res)
  


inf = 100000000000000

ch = input()
B = sum(x == 'B' for x in ch)
S = sum(x == 'S' for x in ch)
C = sum(x == 'C' for x in ch)

a = [int(x) for x in input().split()]
nb = a[0]
ns = a[1]
nc = a[2]

a = [int(x) for x in input().split()]
pb = a[0]
ps = a[1]
pc = a[2]


if B == 0:
    pb = 0
    B = 1
    nb = inf

if S == 0:
    ps = 0
    S = 1
    ns = inf

if C == 0:
    pc = 0
    C = 1
    nc = inf

R = int(input())

l = min(nb//B , ns//S , nc//C)
r = inf
ans = l

def ck(z):
    v = max(0,(B*z-nb)*pb) + max(0,(S*z-ns)*ps) + max(0,(C*z-nc)*pc)
    if v <= R:
        return 1
    return 0

while l <= r:
    mid = (l+r)>>1
    if ck(mid):
        ans = mid
        l = mid+1
    else:
        r = mid-1
print(ans)
###