Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    N = int(input())
    GA, SA, BA = map(int, input().split())
    GB, SB, BB = map(int, input().split())

    def napsac(x, g1, s1, b1, g2, s2, b2):
        dp = [None for _ in range(x+1)]
        dp[0] = 0

        # def case(i, m1, m2):
        #     return 0 if i - m1 < 0 else dp[i-m1] + m2

        # for i in range(1,x+1):
        #     dp[i] = max(i, case(i, g1, g2), case(i, s1, s2), case(i, b1, b2))

        gsbs = ((g1, g2), (s1, s2), (b1, b2))

        for i in range(1,x+1):
            dp[i] = i
            for m in gsbs:
                if m[0] <= i:
                    dp[i] = max(dp[i], dp[i-m[0]] + m[1])
                    
        return dp[-1]

    print(napsac(napsac(N, GA, SA, BA, GB, SB, BB), GB, SB, BB, GA, SA, BA))

if __name__ == "__main__":
    main()

### FIXED CODE ###

N = int(input())
GA, SA, BA = map(int, input().split())
GB, SB, BB = map(int, input().split())

def napsac(x, g1, s1, b1, g2, s2, b2):
    dp = [0 for _ in range(x+1)]
    dp[0] = 0

    def case(i, m1, m2):
        return 0 if i - m1 < 0 else dp[i-m1] + m2

    for i in range(1,x+1):
        dp[i] = max(i, case(i, g1, g2), case(i, s1, s2), case(i, b1, b2))

    return dp[-1]

print(napsac(napsac(N, GA, SA, BA, GB, SB, BB), GB, SB, BB, GA, SA, BA))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
x = 1
for i in range(k):
    x *= a[i]
ls = [x]
for j in range(1,n-k+1):
    x /= a[j-1]
    x *= a[j+k-1]
    ls.append(int(x))
for i in range(1,len(ls)):
    if ls[i] > ls[i-1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
sumf = sum(a[:k])
for i in range(1,n-k+1):
    sumn = sumf - a[i-1] + a[i+k-1]
    print("Yes" if sumn>sumf else "No")
    sumf = sumn
### BUGGY CODE ###

from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0
    q = deque([0])
    cnt = 0
    while q:
        now = q.pop()
        for next in g[now]:
            if prev[next] < 0 or dist[now] + 1 < dist[next]:
                if prev[next] < 0:
                    q.append(next)
                    cnt += 1
                else:
                    q.appendleft(next)
                prev[next] = now + 1
                dist[next] = dist[now] + 1
    if cnt == n:
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0
    q = deque([0])
    cnt = 0
    while q:
        now = q.popleft()
        for next in g[now]:
            if prev[next] < 0:
                if prev[next] < 0:
                    q.append(next)
                    cnt += 1
                prev[next] = now + 1
                dist[next] = dist[now] + 1
    if cnt == n:
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import itertools
from sys import stdin
N=list(map(int,stdin.readline().strip().split()))[0]
st=list(stdin.readline().strip())
count=0
stt=set(st)
stt=list(stt)
num=["0","1","2","3","4","5","6","7","8","9"]
num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]
cnt = 0
for number in num_list:

    for i in range(N):
        if number[cnt]==st[i]:
            cnt+=1
            if cnt==3:
                count += 1
                break
    cnt = 0


print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def binary_search(K, A, F):
    ng = -1
    ok = 10 ** 18
    while ok - ng > 1:
        mid = (ok + ng) // 2
        need_k = sum(max(0, a - mid // f) for a, f in zip(A, F))
        if need_k <= K:
            ok = mid
        else:
            ng = mid
    return ok


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    ans = binary_search(K, A, F)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8[:],i8[:])", cache=True)
def binary_search(K, A, F):
    """Meguru type binary search"""
    ng = -1
    ok = 10 ** 12

    def is_ok(A, F, K, x):
        count = 0
        for a, f in zip(A, F):
            count += max(0, a - x // f)
        return count <= K

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(A, F, K, mid):
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)
    F = np.array(input().split(), dtype=np.int64)

    A.sort()
    F[::-1].sort()

    ans = binary_search(K, A, F)
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
list = list(map(int, input().split()))
ans = 1

max = 10 ** 18

for i in range(n):
    ans = ans * list[i]

if ans > max:
    ans = -1
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))

    if 0 in A:
        print(0)
        return

    ans = 1
    for item in A:
        ans = ans * item
        if ans > 1000000000000000000:
            print(-1)
            return

    print(ans)


main()
### BUGGY CODE ###

def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(1,H+maxA):
        dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

A,B,C,X,Y = map(int, input().split())
ans = 0
for i in range(10**5):
    C = 2*C*i + max(0,X-i)*A + max(0,Y-i)*B
    ans = min(ans, C)
print(ans)  

### FIXED CODE ###

a, b, c, x, y = map(int, input().split())

res = a*x + b*y
for i in range(1, max(x, y)+1):
    ab = i*2
    cand = ab*c + a*max(0, x-i) + b*max(0, y-i)

    res = min(res, cand)

print(res)
### BUGGY CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 1, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for i in range(len(dp_w)):
        w = dp_w[i]
        v = dp_v[i]
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

n=int(input())
csf=[0]
for i in range(n-1):
    csf.append(list(map(int,input().split())))
for i in range(1,n):
    t=0
    for j in range(i,n):
        if t<=csf[j][1]:
            t=csf[j][1]+csf[j][0]
        else:
            k=1
            while True:
                if t<=csf[j][1]+k*csf[j][2]:
                    t=csf[j][1]+k*csf[j][2]+csf[j][0]
                    break
                else:
                    k+=1
    print(t)
print(0)


### FIXED CODE ###

n=int(input())
csf=[0]
for i in range(n-1):
    csf.append(list(map(int,input().split())))
for i in range(1,n):
    t=0
    for j in range(i,n):
        if t<=csf[j][1]:
            t=csf[j][1]+csf[j][0]
        else:
            if t%csf[j][2]!=0:
                t=t+csf[j][2]-t%csf[j][2]+csf[j][0]
            else:
                t+=csf[j][0]
    print(t)
print(0)
### BUGGY CODE ###

s=int(input())
mod=10**9+7


dp=[[0]*(s+1) for _ in range(s)]

for i in range(3,s+1):
    dp[0][i]=1

ans=0
ans+=dp[0][s]

for keta in range(1,s//3+1):
    #print("keta",keta)
    flag=0
    for ss in range(3*keta,s+1):
        for k in range(3,s+1):

            if ss+k<=s:
                dp[keta][ss+k]+=dp[keta-1][ss]
                dp[keta][ss+k]%=mod


    ans+=dp[keta][s]
    ans%=mod

#print(dp)
    

print(ans%mod)






### FIXED CODE ###

s=int(input())
mod=10**9+7

if s<3:
    print(0)
    exit()

dp=[1]*(s+1)

dp[0]=0
dp[1]=0
dp[2]=0

#print(dp)
for i in range(3,s+1):
    for j in range(3,s-i+1):
        dp[i+j]+=dp[i]%mod
    #print(i,dp)
print(dp[s]%mod)
### BUGGY CODE ###

# import decimal
import time
time1 = time.time()

N, K = map(int, input().split())
# N = 200000
# K = 50000
A_list = list(map(int, input().split()))
# A_list = [2 for i in range(N)]
Score_list = [1 for i in range(N+1)]

for i in range(K, N+1):
    if i == K:
        S = 1
        for j in range(i-K, i):
            S *= A_list[j]
        Score_list[i] = S
    else:
        Score_list[i] = int(Score_list[i-1] / A_list[i-1-K])
        Score_list[i] *= A_list[i-1]
    if i > K:
        if Score_list[i] > Score_list[i-1]:
            print("Yes")
        else:
            print("No")
    # print(Score_list)

# print(Score_list)
time2 = time.time()
# print(time2-time1)


### FIXED CODE ###

# import decimal
import time
time1 = time.time()

N, K = map(int, input().split())
# N = 200000
# K = 50000
A_list = list(map(int, input().split()))
# A_list = [2 for i in range(N)]
# Score_list = [1 for i in range(N+1)]

for i in range(K+1, N+1): #KからNの数字が入る
    # print(i-1)
    # print(i-2-K)
    if A_list[i-1] > A_list[i-1-K]:
        print("Yes")
    else:
        print("No")
    # if i == K:
    #     S = 1
    #     for j in range(i-K, i):
    #         S *= A_list[j]
    #     Score_list[i] = S
    # else:
    #     Score_list[i] = int(Score_list[i-1] / A_list[i-1-K])
    #     Score_list[i] *= A_list[i-1]
    # if i > K:
    #     if Score_list[i] > Score_list[i-1]:
    #         print("Yes")
    #     else:
    #         print("No")
    # # print(Score_list)

# print(Score_list)
time2 = time.time()
# print(time2-time1)
### BUGGY CODE ###

N = int(input())
b=[]
for j in range(N):
    a = input()
    if(a in b):
        continue
    else:
        b.append(a)

print(len(b))


### FIXED CODE ###

N = int(input())
b=[]
c=[]
for j in range(N):
    a = input()
    b.append(a)



c = set(b)

print(len(c))
### BUGGY CODE ###

def main():
    n =int( input())
    sn=[]

    for i in range(n):
        inWord = str(input())
        addFlag = True
        for s in sn:
            if s["word"] == inWord and len(sn) !=0:
                s["count"]+=1
                addFlag = False
                break
        if addFlag ==True:
            sn.append( {"word":inWord,"count":1})
    
    sn.sort(reverse=True,key=lambda x:x['count'])
    
    most = int(sn[0]["count"])
    mostWords=[]
    for elm in sn:
        if elm["count"] == most:
            mostWords.append(elm["word"])
        else:
            break
        
    mostWords.sort()

    for elm in mostWords:
        print(elm)
    return
main()



### FIXED CODE ###

def main():
    n =int( input())

    cnt=dict()
    
    for _ in range(n):
        s=input()
        if s in cnt:
            cnt[s]+=1
        else :
            cnt[s]=1
    #print(cnt)
    
    num = 0
    res =[]
    for key,value in cnt.items():
        #print(key,":::",value)
        if value > num:
            num=value
            res=[]
            res.append(key)

        elif value==num:
            res.append(key)

    #print("res::",res)

    
    #a = [k for k, v in cnt.items() if v == max(cnt.values())]


    #print("結果発表：：：：",len(res))
    res.sort()
    for elm in res:
        print(elm)


main()
### BUGGY CODE ###

def hoge(z):
    yuki = 0
    for i in range(2, z):
        if z % i == 0:
            yuki += 1
        if yuki:
            return False
    return True

if __name__ == '__main__':
    n = int(input())
    c = 0
    for _ in range(n):
        if hoge(int(input())):
            c += 1
    print (c)


### FIXED CODE ###

import math

def isprime(z):
    if z == 2:
        return True
    
    if z < 2 or z % 2 == 0:
        return False
    i = 3
    while i <= math.sqrt(z):
        if z % i == 0:
            return False
        i += 2
    return True

if __name__ == '__main__':
    n = int(input())
    c = 0
    for _ in range(n):
        if isprime(int(input())):
            c += 1
    print (c)
### BUGGY CODE ###

N = int(input())
m = (N - 1)
n = 0
while m > 0:
    n = n + (m % N)
    N = m
    m = m - 1
print(n)


### FIXED CODE ###

N = int(input())
print((N * (N - 1)) // 2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

MOD = 10**9+7

# input
N = int(input())
C = list(map(int, input().split()))
    
# process
C.sort()
ans = 0

# d:数列S、Tの異なる整数の数、idx:加算するコストの開始インデックス
def f(d, idx):
    if d == 0 or d + idx > N:
        return 1, 0

    t = 0
    cnt = 0
    for i in range(idx, N-d+1):
        c, r = f(d-1, i+1)
        t += d*C[i]*c + r
        cnt += c

    
    return cnt, t

ans = 0
for i in range(1, N+1):
    c, r = f(i, 0)
    ans += r
#    print("ans,r: {},{}".format(ans,r))

# output
print(ans*2**N%MOD)


### FIXED CODE ###

#import sys
#sys.setrecursionlimit(10**5)
MOD = 10**9+7

# input
N = int(input())
C = list(map(int, input().split()))
    
# process
C.sort(reverse=True)
ans = 0

if N == 1:
    ans = C[0]*2**N
else:
    for i in range(N):
        ans += C[i]*(2+i)

    ans *= 4**(N-1)

# output
print(ans%MOD)
### BUGGY CODE ###

from collections import deque

H,W=[int(i) for i in input().split()]
C=[input() for _ in range(H)]
C=[list(i) for i in C] 

ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]

if C[0][0] == "#": 
    stack = deque([[0, 0, 1]])
    visited_list[0][0] = 1
else:
    stack = deque([[0, 0, 0]])
    visited_list[0][0] = 0

def dfs(town, visited_list, stack):
    global ans
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1:
            # print(h,w,cnt)
            if ans > cnt:
                ans = cnt
                continue
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  visited_list[new_h][new_w] > cnt and town[new_h][new_w] != "#":
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif visited_list[new_h][new_w] > cnt + 1 and town[new_h][new_w] == "#":
                visited_list[new_h][new_w] = cnt + 1
                # print("a " + str(cnt+1))
                stack.append([new_h, new_w, cnt+1])
    return ans

print(dfs(C, visited_list, stack))

### FIXED CODE ###

from collections import deque

H,W=[int(i) for i in input().split()]
C=[input() for _ in range(H)]
C=[list(i) for i in C] 

ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]

if C[0][0] == "#": 
    stack = deque([[0, 0, 1]])
    visited_list[0][0] = 1
else:
    stack = deque([[0, 0, 0]])
    visited_list[0][0] = 0

def dfs(town, visited_list, stack):
    global ans
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            continue
        for j, k in ([1, 0], [0, 1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  town[new_h][new_w] != "#" and visited_list[new_h][new_w] > cnt:
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[h][w] == "#" and town[new_h][new_w] == "#" and visited_list[new_h][new_w] > cnt:
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[new_h][new_w] == "#" and visited_list[new_h][new_w] > cnt + 1:
                visited_list[new_h][new_w] = cnt + 1
                # print("a " + str(cnt+1))
                stack.append([new_h, new_w, cnt+1])
    return ans

print(dfs(C, visited_list, stack))
### BUGGY CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * (2 ** N)
for k in range(1, 2 ** N):
    dp[k] = [(A[0], 0), (A[k], k)]

digits = []
k = 1
while k < 2 ** N:
    digits.append(k)
    k <<= 1

for bit in range(2, N + 1):
    for ds in itertools.combinations(digits, bit):
        k = sum(ds)
        for rm in ds:
            dp[k] += dp[k - rm]
        ss = sorted(set(dp[k]))
        dp[k] = ss[-1], ss[-2]

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = input()

# search A
listA = []
for i in range(len(s)):
    if s[i] == "A":
        listA.append(i)

cnt = 0
updated = True
while updated:
    newlist = []
    updated = False
    for i in range(len(listA)):
        if "C" in s[listA[i]:] == False:
            # このAはレンジ外になるのでもう使わない
            pass
        if "B" in s[listA[i]:] == False:
            # このAはレンジ外になるのでもう使わない
            pass
        elif s[listA[i] : listA[i] + 3] == "ABC":
            cnt += 1
            s = s[:listA[i]] + "BCA" + s[listA[i] + 3:]
            #print("i={}, s={}".format(i, s))
            newlist.append(listA[i] + 2)
            updated = True
        else:
            newlist.append(listA[i])
    listA = newlist

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
s = input()

s = s.replace("BC", "*")

point = 0
charge = 0
for i in range(len(s) - 1, -1, -1):
    if s[i] == "*":
        charge += 1
    elif s[i] == "A":
        point += charge
    else:
        charge = 0

print(point)