Harryxun/stf_run huggingface dataset:
#import numpy as np
#import collections
#import math

#f = open('./input_E.txt')
#
#N,K = map(int, f.readline().split())
#A = list(map(int, f.readline().split()))

N,K = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

All_length = sum(A)
KK = K+N-1
lm = All_length/KK

k_list = [int(Ai//lm) for Ai in A]
X_list = [Ai%lm for Ai in A]

sum_k = sum(k_list)
res_cut = KK-sum_k

zero_k = 0
for i in range(1,N+1):
    if k_list[-i] == 0:
        zero_k +=1
    else:
        break

if res_cut > 0:
    ans_kouho = []
    for i in range(-zero_k,0):
        ans_kouho.append(X_list[i])
    for i in range(res_cut):
        for j in range(N-zero_k):
            ans_kouho.append((X_list[j]-i*lm)/k_list[j])
    
    ans_kouho.sort(reverse=True)
    ans = ans_kouho[res_cut] + lm
    ans = int(ans)+1
else:
    ans = int(lm)+1
print(ans)

### FIXED CODE ###

#import numpy as np
#import collections
#import math

#f = open('./input_E.txt')
#
#N,K = map(int, f.readline().split())
#A = list(map(int, f.readline().split()))

N,K = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

def nibu(small,big,KK,AA):
    mid = (small+big)//2
    k_list = [(x-1)//mid for x in AA]
    sum_k = sum(k_list)
    if sum_k <= KK: #達成可能 -> 答えはもっと小さい
        return small,mid # 不可能,可能
    else:
        return mid,big # 不可能,可能


if K==0:
    ans = A[0]
else:    
    lmin = 0
    lmax = A[0]
    
    while lmax - lmin >= 2:
        lmin, lmax = nibu(lmin,lmax,K,A)
    
    ans = lmax
    
print(ans)
import collections
import math

n = int(input())
sl = collections.Counter([str(sorted(input())) for _ in range(n)])

ret = 0
for _, v in sl.most_common():
    if 2 <= v:
        ret += math.factorial(v) / math.factorial(2) / math.factorial(v - 2)

print(int(ret))


### FIXED CODE ###

import collections

n = int(input())
sl = collections.Counter([str(sorted(input())) for _ in range(n)])

ret = 0
for _, v in sl.most_common():
    if 2 <= v:
        ret += v * (v - 1) // 2

print(ret)
from sys import stdin
import math


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 2**math.floor(math.log2(N))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin
import math


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 2**math.floor(math.log(N,2))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
N,Q=map(int,input().split())
S=input()
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
  l[i],r[i]=map(int,input().split())
  print(S[l-1:r].count('AC'))
  

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(0,N-1):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(0,Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])
N = int(input())
A = list(map(int, input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
elif A[0] != 0:
    print(-1)
else:
    rest = [1]
    for i in range(1, N+1):
        rest.append(min(rest[i-1]*2 - A[i], 10**13))
    ans, cnodes = A[N], A[N]
    for i in range(N-1, -1, -1):
        if cnodes//2 + cnodes%2 > rest[i]:
            print(-1)
            exit()
        else:
            cnodes = min(cnodes, rest[i]) + A[i]
            ans += cnodes
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
elif A[0] != 0:
    print(-1)
else:
    rest = [1]
    for i in range(1, N+1):
        rest.append(min(rest[i-1]*2 - A[i], 10**13))
    ans, cnodes = A[N], A[N]
    for i in range(N-1, -1, -1):
        if cnodes//2 + cnodes%2 > rest[i]:
            print(-1)
            exit()
        else:
            cnodes = min(cnodes, rest[i]) + A[i]
            ans += cnodes
    print(ans)
# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())
N = int(input())

if N%2 == 1 :
  print (0)
else :
  cnt = 0
  i = 1
  N //= 2
  while N >= 5**i :
    cnt += N // (5**i)
    i += 1
    
print (cnt)
  
  

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())
N = int(input())

if N%2 == 1 :
  print (0)
  exit()
else :
  cnt = 0
  i = 1
  N //= 2
  while N >= 5**i :
    cnt += N // (5**i)
    i += 1
    
  print (cnt)
# ABC170

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

a.sort()
a_max = max(a)
dp = [True for _ in range(a_max+1)]

ans = 0
for i in range(n):
    if dp[a[i]]:
        for j in range(0, a_max+1, a[i]):
            dp[j] = False
        if (a[i] != a[i-1]) and (a[i] != a[i+1]):
            ans += 1

print(ans)


### FIXED CODE ###

# ABC170

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

a.sort()
a_max = max(a)
dp = [True for _ in range(a_max+1)]

ans = 0
for i in range(n):
    if dp[a[i]]:
        for j in range(0, a_max+1, a[i]):
            dp[j] = False
        if i > 0:
            if a[i] == a[i-1]:
                continue
        if i < n-1:
            if a[i] == a[i+1]:
                continue
        ans += 1

print(ans)
S = input()
print("No" if "L" in "S[0::2] or "R" in S[1::2] else "Yes")

### FIXED CODE ###

S = input()
print("No" if "L" in S[0::2] or "R" in S[1::2] else "Yes")
def exe(x, y):
  X = [0] * x
  Y = [0] * y
  for i in range(x):
    X[i] = (i + 1) * (x - i) * a[i] % MOD
  for i in range(y):
    Y[i] = (i + 1) * (y - i) * b[i] % MOD
  print((sum(X) % MOD) * (sum(Y) % MOD) % MOD)
  

n, m = list(map(int, input().split()))
x = list(map(int, input().split()))
y = list(map(int, input().split()))
MOD = 10 ** 9 + 7
a = [0] * (n - 1)
for i in range(n - 1):
  a[i] = x[i + 1] - x[i]
b = [0] * (n - 1)
for i in range(m - 1):
  b[i] = y[i + 1] - y[i]
exe(n - 1, m - 1)

### FIXED CODE ###

n, m = list(map(int, input().split()))
x = list(map(int, input().split()))
y = list(map(int, input().split()))
MOD = 10 ** 9 + 7
X = 0
Y = 0
for i in range(n - 1):
  t = x[i + 1] - x[i]
  X = (X + (i + 1) * (n - i - 1) * t) % MOD
for i in range(m - 1):
  t = y[i + 1] - y[i]
  Y = (Y + (i + 1) * (m - i - 1) * t) % MOD
print(X * Y % MOD)
data = map(int,input().split())
for i in range(data[2]):
  if data[0] >= 1:
    data[0] -= 1
  elif data[1] >=1:
    data[1] -=1
print(f'{data[0]} {data[1]}')

### FIXED CODE ###

a,b,k = map(int, input().split())
if a <= k:
    k -= a
    if b <= k:
        k -= b
        print(0,0)
    else:
        print(0,b-k)
else:
    print(a-k,b)
N = int(input())
a = [list(map(int, input().split()))]
a = a.sort()
array = []
for i in range(N):
  array = array.append(a[3*N-2*(i+1)])
ans = sum(array)
print(ans)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

ans = sum(a[2*i-1] for i in range(1,N+1))
print(ans)
from itertools import permutations

n, m = map(int, input().split())
# a, b = [], []
paths = set()

for i in range(n) :
    _a, _b = map(int, input().split())
    paths.add((_a, _b))
    paths.add((_b, _a))
    
print(sum(all((s, t) in paths for s, t in zip((1,) + p, p)) for p in permutations(range(2, n + 1))))



### FIXED CODE ###

from itertools import permutations

n, m = map(int, input().split())
paths = set()

for i in range(m) :
    _a, _b = map(int, input().split())
    paths.add((_a, _b))
    paths.add((_b, _a))
    
print(sum(all(s in paths for s in zip((1,) + p, p)) for p in permutations(range(2, n + 1))))
n=int(input())
x=[0 for i in range(n)]
y=[0 for i in range(n)]
for i in range(n):
    x[i]=input()
    y[i]=input()

for i in range(n):
    X=list(x[i])
    Y=list(y[i])
    a=[int(0) for i in range(len(X))]
    for j in range(len(X)):
        b=-1
        for l in range(j,len(X)):
            for k in range(len(Y)):
                if X[l]==Y[k] and b<k:
                    b=k
                    a[j]+=1
                    break
                
    print(max(a))
a=[0 for i in range(n)]a=[0 for i in range(n)]


### FIXED CODE ###

def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]#スライス
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
    
n = int(input().rstrip())#rstripで余計な空白削除
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")
N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
INF = 100000
dp = [[INF]*N+1 for _ in range(N+1)] #dp[i,j]:Aがiグラム、Bがjグラムの時の最小予算
dp[0][0] = 0 
from itertools import product as prd
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in prd(R(a),R(b)):
        dp[i][j] = min(dp[i][j], dp[i-a][j-b]+c)

ans = INF
for i,j in prd(R(1),R(1)):
    if i*Mb == j*Ma:
        ans = min(ans, dp[i][j])
print(ans if ans != INF else -1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
c = [0,2,5,5,4,5,6,3,7,6]
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

B = [0] * M
for i in range(M):
    B[i] = c[A[i]]

x = min(B)
value = 0
for i in range(M):
    if B[i] == x:
        value = max(A[i], value)
y = N % x
if y == 0:
    print(str(value) * (N / x))
else:
    k = 10
    for i in range(M):
        if B[i] % x == y:
            if k > B[i]:
                k = B[i]
                l = A[i]
            elif k == B[i]:
                l = max(l, A[i])
    if value > l:
        print(str(value) * ((N - k) // x) + str(l))
    else:
        print(str(l) + str(value) * ((N - k) / x))

### FIXED CODE ###

def f(x):
    k = int(x)
    return c[k], k


c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = list(map(f, input().split()))
A = sorted(A, key=lambda x: x[0] * 10 - x[1])

# 数字を作成するのに必要なマッチ数のリストを作成
b = []
dic = {}
n = 0
for d in A:
    if n != d[0]:
        b.append(d[0])
        n = d[0]
        dic[n] = d[1]

ans = [0] * b[0]
n = b[0]
while True:
    max_ = 0
    for d in b:
        if n - d == 0:
            if dic[d] > max_:
                max_ = dic[d]
        elif n - d > 0 and ans[n - d] > 0:
            t = ans[n - d] * 10 + dic[d]
            max_ = max(max_, t)

    if n == N:
        print(max_)
        break
    ans.append(max_)
    n += 1
testSNs = raw_input().split()
SCORE=int(0)
for x in range(testSNs[0]):
    if not testSNs[x]%10 is 0:
        SCORE += testSNs[x]
    else:
        continue
print(SCORE)

### FIXED CODE ###

x = list(map(int, input().split()))
if x[0]+x[1]<10:
    print(x[0]+x[1])
else:
    print('error')
import itertools
import sys


c = list(itertools.product(range(10), repeat=4))

for n in sys.stdin.readlines():
    print sum([l for l in c if int(n) == sum(l)])

### FIXED CODE ###

import sys


for n in sys.stdin:
    ret = 0
    for a in xrange(10):
        for b in xrange(10):
            for c in xrange(10):
                for d in xrange(10):
                    if a+b+c+d == int(n):
                        ret += 1
    print ret
# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/
#
# lang: Python3 (3.4.3)

import math
import statistics
import numpy as np
import queue

n,m,k = map(int, input.split())
for i in range(n):
  for j in range(m):
    if i * (m - j) + j * (n - i) == k:
      print('Yes')
    else:
      print('No')


### FIXED CODE ###

# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/
#
# lang: Python3 (3.4.3)

import math
import statistics
import numpy as np
import queue

n,m,k = map(int, input().split())
for i in range(n + 1):
  for j in range(m + 1):
    if n * j + m * i - 2 * i * j == k:
      print('Yes')
      exit(0)
print('No')
import collections

N = int(input())
A = list(map(int, input().split()))
A = collections.Counter(A)
B = []
C = []
for i in A:
    if A[i] == 1:
        B.append(i)
    else:
        C.append(i)
B = sorted(B)
if len(B) == 0:
    print(0)
    exit()
mb = B[-1]
ok = [True] * (mb+1)

if len(C) > 0:
    C = sorted(C)
    for c in C:
        if not ok[c]:
            continue
        k = 2
        while k*c <= mb:
            ok[k*c] = False
            k += 1

for b in B:
    if not ok[b]:
        continue
    k = 2
    while k*b <= mb:
        ok[k*b] = False
        k += 1

ans = 0
for b in B:
    if ok[b]:
        ans += 1

print(ans)


### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
A = collections.Counter(A)
B = []
C = []
for i in A:
    if A[i] == 1:
        B.append(i)
    else:
        C.append(i)
B = sorted(B)
if len(B) == 0:
    print(0)
    exit()
mb = 1000000
ok = [True] * (mb+1)

if len(C) > 0:
    C = sorted(C)
    for c in C:
        if not ok[c]:
            continue
        k = 2
        while k*c <= mb:
            ok[k*c] = False
            k += 1

for b in B:
    if not ok[b]:
        continue
    k = 2
    while k*b <= mb:
        ok[k*b] = False
        k += 1

ans = 0
for b in B:
    if ok[b]:
        ans += 1

print(ans)
k = int(input())
if k %2 == 0:
	print(int(k*k/2/2)
elif k%2 ==1:
          print(int((k/2)*(k//2)/2)


### FIXED CODE ###

k = int(input())
if k %2 == 0:
  print(int(k*k/2/2))
elif k%2 ==1:
  print(int((k//2 + 1)*(k//2)))
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)

@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    
    mod = x % (bin(x).count('1'))
    return f(mod) + 1


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    pc = X.count('1')
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N-1,-1,-1):
        if Y[i] == '1':
            tmp = (O - pre) % (pc - 1)
        else:
            tmp = (O + pre) % (pc + 1)
        ans[i] = f(tmp) + 1
        pre *= 2

    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    ac_now = now % ac
    if dc:
        dc_now = now % dc
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (dc_now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (ac_now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



if __name__ == "__main__":
    main()
from collections import deque
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

reds = deque(p)
greens = deque(q)
uncolor = deque(r)

# できるだけ値が大きいやつを使いたい
ans = 0
red_cnt = 0
green_cnt = 0
while True:
    # print(red_cnt, green_cnt, reds, greens, uncolor)
    if red_cnt == x and green_cnt == y:
        break
    if len(reds) == 0 or red_cnt == x:
        if greens[0] > uncolor[0]:
            eat = greens.popleft()
        else:
            eat = uncolor.popleft()
        ans += eat
        green_cnt += 1
    elif len(greens) == 0 or green_cnt == y:
        if reds[0] > uncolor[0]:
            eat = reds.popleft()
        else:
            eat = uncolor.popleft()
        ans += eat
        red_cnt += 1
    else:
        if red_cnt < x:
            if reds[0] > greens[0]:
                if reds[0] > uncolor[0]:
                    eat = reds.popleft()
                else:
                    eat = uncolor.popleft()
                ans += eat
                red_cnt += 1
            else:
                if greens[0] > uncolor[0]:
                    eat = greens.popleft()
                else:
                    eat = uncolor.popleft()
                ans += eat
                green_cnt += 1
        else:
            if greens[0] > uncolor[0]:
                eat = greens.popleft()
            else:
                eat = uncolor.popleft()
            ans += eat
            green_cnt += 1
print(ans)





### FIXED CODE ###

from collections import deque
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
p = p[:x]
q.sort(reverse=True)
q = q[:y]
r.sort(reverse=True)
apples = p + q + r
apples.sort(reverse=True)
ans = sum(apples[:x+y])

print(ans)
n = int(input())
s_input = input() 

def judge(s,count):
    if s.count("#.")==0:
        return count

    next=""
    for i in range(0,n-1):
        if s[i]=="#" and s[i+1]==".":
            next1 = s[:i] + "##"
            if i<n-2:
                next1+=s[i+2:]
            pat1 = judge(next1,count+1)

            pat2=pat1
            if i > 0 and s[i-1]==".":
                next2 = s[:i] + ".."
                if i < n-2:
                    next2+=s[i+2:]
                pat2 = judge(next2,count+1)
            return min(pat1,pat2)
    return count

print(judge(s_input,0))

### FIXED CODE ###

n = int(input())
s_input = input() 

check=s_input.count('.')
ans=check
for s in s_input:
    if s=='.':
        # 変えんでいい
        check-=1
    else:
        check+=1
    ans=min(ans,check)
print(ans)
a = list(map(int, input().split()))

print(a.index("0"))

### FIXED CODE ###

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

print(a.index(0)+1)
N, H, W = [int(x) for x in raw_input().split(' ')]
arr = []
for _ in xrange(N):
    r, c, a = [int(x) for x in raw_input().split(' ')]
    arr.append((a, r-1, c+H-1))
arr = sorted(arr)
ans = 0
P = [-1] * (H+W)
C = [1] * (H+W)

def find(a):
    if P[a] < 0:    return a
    t = find(P[a])
    P[a] = t
    return t

def unite(r, c):
    fr, fc = find(r), find(c)
    if fr == fc:  return 0
    C[fr] = C[fc] = C[fr] + C[fc]
    if P[fr] == P[fc]:
        P[fc] = fr
        P[fr] -= 1
    elif P[fr] > P[fc]:
        P[fc] = fr
    else:
        P[fr] = fc
    
while arr:
    a, r, c = arr.pop()
    unite(r, c)
    if C[find(r)]:
        ans += a
        C[find(r)] -= 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    C[par(a)], C[par(b)] = C[par(a)] + C[par(b)], C[par(a)] + C[par(b)]
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)
N, H, W = map(int, input().split())
P = [-1 for i in range(H+W)]
C = [1] * (H+W)
X = []
for _ in range(N):
    r, c, a = map(int, input().split())
    X.append((a, r-1, c+H-1))
X = sorted(X)
ans = 0
while X:
    a, r, c = X.pop()
    unite(r, c)
    if C[par(r)]:
        ans += a
        C[par(r)] -= 1
print(ans)
N=int(input())
A=[]
B=[]
C=[]
for i in range(N):
  a,b,c=map(int,input().split())
  A.append(a)
  B.append(b)
  C.append(c)
dp=[[0 for i in range(N)]for j in range(N)]
dp[0][0]=A[0]
dp[0][1]=B[0]
dp[0][2]=C[0]
for i in range(1,N):
  dp[i]=[max(dp[i-1][1]+A[i],dp[i-1][2]+A[i]),max(dp[i-1][0]+B[i],dp[i-1][2]+B[i]),max(dp[i-1][0]+C[i],dp[i-1][1]+C[i])]
print(max(dp[N-1][0],dp[N-1][1],dp[N-1][2]))

### FIXED CODE ###

N=int(input())
a,b,c=map(int,input().split())
dp=[[0 for i in range(3)]for j in range(N)]
dp[0]=[a,b,c]
for i in range(1,N):
  A,B,C=map(int,input().split())
  dp[i]=[max(dp[i-1][1]+A,dp[i-1][2]+A),max(dp[i-1][0]+B,dp[i-1][2]+B),max(dp[i-1][0]+C,dp[i-1][1]+C)]
print(max(dp[N-1][0],dp[N-1][1],dp[N-1][2]))
import numpy as np
N = int(input())
S = np.empty(5, dtype=str)
for i in range(N):
    S[i] = input()

S_M = np.array([S[i] for i in range(N) if S[i][0] == 'M'])
S_A = np.array([S[i] for i in range(N) if S[i][0] == 'A'])
S_R = np.array([S[i] for i in range(N) if S[i][0] == 'R'])
S_C = np.array([S[i] for i in range(N) if S[i][0] == 'C'])
S_H = np.array([S[i] for i in range(N) if S[i][0] == 'H'])

souwa = 0
kahi = np.array([0, 0, 0, 0, 0])
kahi[0] = len(S_M)
kahi[1] = len(S_A)
kahi[2] = len(S_R)
kahi[3] = len(S_C)
kahi[4] = len(S_H)

kahi_not0 = kahi[kahi != 0]
if len(kahi_not0) <= 2:
    print(0)
else:
    for i in range(len(kahi_not0)-2):
        for j in range(i+1, len(kahi_not0)-1):
            for k in range(j+1, len(kahi_not0)):
                souwa += kahi_not0[i]*kahi_not0[j]*kahi_not0[k]

    print(souwa)

### FIXED CODE ###

import numpy as np
N = int(input())
S = [None]*N
for i in range(N):
    S[i] = input()

S_M = [S[i] for i in range(N) if S[i][0] == 'M']
S_A = [S[i] for i in range(N) if S[i][0] == 'A']
S_R = [S[i] for i in range(N) if S[i][0] == 'R']
S_C = [S[i] for i in range(N) if S[i][0] == 'C']
S_H = [S[i] for i in range(N) if S[i][0] == 'H']

souwa = 0
kahi = [0]*5
kahi[0] = len(S_M)
kahi[1] = len(S_A)
kahi[2] = len(S_R)
kahi[3] = len(S_C)
kahi[4] = len(S_H)

for i in range(len(kahi)-2):
    for j in range(i+1, len(kahi)-1):
        for k in range(j+1, len(kahi)):
            souwa += kahi[i]*kahi[j]*kahi[k]
print(souwa)
N = int(input())
u, v, w = [0]*(N-1), [0]*(N-1), [0]*(N-1)
n = [-1] * N 
# n[][0] 色　n[][1] 連結先一覧リスト(連結先奇数なら+ 偶数なら-がかかる1追加された値)
for i in range(N):
    n[i] = [0]*3
    n[i][1] = []


for i in range(N-1):
    u[i], v[i], w[i] = list(map(int, input().split()))
    n[u[i]-1][1].append((v[i])*(w[i]%2*2 -1))
    n[v[i]-1][1].append((u[i])*(w[i]%2*2 -1))

# n[][2] 探索済フラグ
def dfs(num):
    n[num][2] = 1
    for item in n[num][1]:
        if n[abs(item)-1][2] == 0:
            if item < 0:
                item = -1*item
                n[item-1][0] = n[num][0]
                dfs(item-1)
            else:
                n[item-1][0] = -1 * n[num][0] +1
                dfs(item-1)

dfs(u[0]-1)

for i in n:
    print(i[0])

### FIXED CODE ###

N = int(input())
u, v, w = [0]*(N-1), [0]*(N-1), [0]*(N-1)
n = [-1] * N
# n[][0] 色　n[][1] 連結先一覧リスト n[][2] mod2 
for i in range(N):
    n[i] = [0]*4
    n[i][1] = []
    n[i][2] = []

for i in range(N-1):
    u[i], v[i], w[i] = list(map(int, input().split()))
    n[u[i]-1][1].append(v[i]-1)
    n[v[i]-1][1].append(u[i]-1)
    n[u[i]-1][2].append(w[i]%2)
    n[v[i]-1][2].append(w[i]%2)

stack = [u[0]-1]

while True:
    num = stack.pop()
    n[num][3] = 1
    for i in range(len(n[num][1])):
        if n[n[num][1][i]][3] == 0:
            stack.append(n[num][1][i])
            if n[num][2][i] == 0:
                n[n[num][1][i]][0] = n[num][0]
            else:
                n[n[num][1][i]][0] = -1 * n[num][0] + 1
    if len(stack) == 0:
        break

for i in n:
    print(i[0])
for i in range(1,100000000000)
    x = int(input())
    if x == 0:
        break
    print("Case " + str(i) + ": " + str(x))

### FIXED CODE ###

for i in range(1,10005):
    x = int(input())
    if x == 0:
        break
    print("Case " + str(i) + ": " + str(x))