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

import queue
n = int(input())

#ab = [[]*(n)]
ab = [[] for _ in range(n+1)]
#print(ab)

li = []

for i in range(n-1):
    a,b = map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
    li.append([a,b])
    
ab_color = [[0 for _ in range(n+1)] for _ in range(n+1)]

#print(li)

q = queue.Queue()
check = [0] * (n+1)
#check[1] == 1
check_color = [0] * (n+1)

q.put(1)
color_num = 1
#mae_color = 0

while not q.empty():
    tmp_color = 0
    tmp = q.get()
    #print(tmp)
    #tmp_color = mae_color
    mae_color = check_color[tmp]
    for i in range(len(ab[tmp])):
        if check[ab[tmp][i]] == 1:
            #print(i,tmp)
            continue
        else:
            #print(mae_color,tmp_color,tmp,i)
            tmp_color += 1
            q.put(ab[tmp][i])
            if tmp_color == mae_color:
                tmp_color += 1
            check_color[ab[tmp][i]] = tmp_color
            ab_color[ab[tmp][i]][tmp] = tmp_color
            ab_color[tmp][ab[tmp][i]] = tmp_color
            check[tmp] = 1
            color_num = max(color_num,tmp_color)
            #print(check,i)

print(color_num)
for i in range(len(li)):
    print(ab_color[li[i][0]][li[i][1]])

### FIXED CODE ###

import queue
n = int(input())


#ab = [[]*(n)]
ab = [[] for _ in range(n+1)]
#print(ab)

li = []

for i in range(n-1):
    a,b = map(int,input().split())
    ab[a].append([b,i])
    ab[b].append([a,i])
    #li.append([a,b])

#ab_color = [[None for _ in range(n+1)] for _ in range(n+1)]
ans = [0] * (n-1)

q = queue.Queue()
check = [0] * (n+1)
#check[1] == 1
check_color = [0] * (n+1)

q.put(1)
color_num = 1
#mae_color = 0

while not q.empty():
    tmp_color = 0
    tmp = q.get()
    #print(tmp)
    #tmp_color = mae_color
    mae_color = check_color[tmp]
    for i in range(len(ab[tmp])):
        if check[ab[tmp][i][0]] == 1:
            #print(i,tmp)
            continue
        else:
            #print(mae_color,tmp_color,tmp,i)
            tmp_color += 1
            q.put(ab[tmp][i][0])
            if tmp_color == mae_color:
                tmp_color += 1
            check_color[ab[tmp][i][0]] = tmp_color
            ans[ab[tmp][i][1]] = tmp_color
            #ab_color[ab[tmp][i]][tmp] = tmp_color
            #ab_color[tmp][ab[tmp][i]] = tmp_color
            check[tmp] = 1
            if color_num < tmp_color:
                color_num = tmp_color
            #color_num = max(color_num,tmp_color)
            #print(check,i)

print(color_num)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
datas = [int(input()) for _ in range(N)]
diff = max(datas[1:]) - datas[0]

for i in range(1,N-1):
    new_diff = max(datas[i+1:]) - datas[i]
    if diff < new_diff:
        diff = new_diff

print(diff)


### FIXED CODE ###

from sys import stdin

N,*datas = [int(i) for i in stdin.readlines()]
now_max = max(datas[1:])
max_index = datas.index(now_max)
diff = now_max - datas[0]

for i in range(1,N-1):
    if i == max_index:
        now_max = max(datas[i+1:])
        max_index = datas.index(now_max,i+1)
    new_diff = now_max - datas[i]
    if diff < new_diff:
        diff = new_diff

print(diff)
### BUGGY CODE ###

N = int(input())
S = list(input())

ans_lst = [float("inf")]*(N)
for i in range(0,N):
    ans_lst[i] = S[:i].count("W") + S[i+1:].count("E")
ans = min(ans_lst)
print(ans)


### FIXED CODE ###

N = int(input())
S = list(input())

lst = [0]*N
Re = S.count("E")
Lw = 0

for i in range(N):
    if S[i] == "E":
        Re -= 1
        lst[i] = Re + Lw
    else:
        Lw += 1
        lst[i] = Re + Lw - 1

ans = min(lst)
print(ans)
### BUGGY CODE ###

from itertools import accumulate

def e(dice):
    return sum([r / dice for r in range(1, dice+1)])

n, k = map(int, input().split())
p = list(map(int, input().split()))

p_cum = [0] + list(accumulate(p))

ma = 0
ind = 0
for i in range(k, n+1):
    if ma < p_cum[i] - p_cum[i-k]:
        ma = p_cum[i] - p_cum[i-k]
        ind = i

x = p[ind-k:ind]

print(sum(e(d) for d in x))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from itertools import accumulate

    def e(dice):
        ans = 0
        for r in range(1, dice+1):
            ans += r /dice
        return ans

    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    p_cum = [0] + list(accumulate(p))

    ma = 0
    ind = 0
    for i in range(k, n+1):
        temp = p_cum[i] - p_cum[i-k]
        if ma < temp:
            ma = temp
            ind = i

    x = p[ind-k:ind]

    print(sum(e(d) for d in x))

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



from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    nxt = defaultdict(set)

    A = [list(map(int, input().split())) for _ in range(N)]

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                nxt[b].add((l,h))
                b = (l,h)



    match_today = deque()

    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
                

    match_tomorrow = deque()
    ans = 0
    cnt_match = 0 
    while len(match_today) > 0:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_tomorrow.append((nl, nh))
        
        match_today = match_tomorrow
        match_tomorrow = deque()


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

lastans = -1e20

for i in range(n):
    now = p[i] - 1 
    score = [c[now]]
    while True:
        now = p[now] - 1
        score.append(score[-1] + c[now])
        if now == i:
            break
    loopsum = score[-1]
    looplen = len(score)
#    print(score)
    if looplen >= k:
        ans = max(score[:k])
    elif loopsum <= 0:
        ans = max(score)
    else:
        loopnum = k//looplen
        loopnum_mod = k % looplen
        ans1 = loopsum * (loopnum - 1) + max(score)
        ans2 = loopsum * loopnum
        if loopnum_mod != 0:
            ans2 = ans2 +max(0,max(score[:loopnum_mod]))
        ans =max(ans1,ans2)
    lastans = max(lastans,ans)

print(lastans)



### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

lastans = -1e20

for i in range(n):
    now = p[i] - 1 
    score = [c[now]]
    while True:
        now = p[now] - 1
        score.append(score[-1] + c[now])
        if now == i:
            break
    loopsum = score[-1]
    looplen = len(score)
#    print(score)
    if looplen >= k:
        ans = max(score[:k])
    elif loopsum <= 0:
        ans = max(score)
    else:
        loopnum = k//looplen
        loopnum_mod = k % looplen
        ans1 = loopsum * (loopnum - 1) + max(score)
        ans2 = loopsum * loopnum
        if loopnum_mod != 0:
            ans2 = ans2 +max(0,max(score[:loopnum_mod]))
        ans =max(ans1,ans2)
    lastans = max(lastans,ans)

print(lastans)
### BUGGY CODE ###

n,k=map(int, input().split())
p=[int(i) for i in input().split()]

ans=0
for i in range(n-k+1):
  tmp=0
  for j in range(k):
    tmp+=(p[i+j]+1.0)/2.0
  ans = max(ans, tmp)
print('{:.12f}'.format(ans))


### FIXED CODE ###

n, k = map(int, input().split())
p = [(int(i)+1.0)/2.0 for i in input().split()]
ans = 0
for i in range(k):
    ans += p[i]
tmp1 = ans
for i in range(k, n):
    tmp2 = (tmp1 - p[i-k])+p[i]
    ans = max(ans, tmp2)
    tmp1 = tmp2
print('{:.12f}'.format(ans))
### BUGGY CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

H, W = [int(x) for x in input().split()]
L = []
for _ in range(H):
    L.append(list(input()))

dx = [1, -1, 0, 0, 0]
dy = [0, 0, 1, -1, 0]


def check(M):
    return all([x == '#' for x in sum(M, [])])


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False


def f(m1):
    ret = [['.'] * W for _ in range(H)]
    for x in range(W):
        for y in range(H):
            for i in range(5):
                X = x + dx[i]
                Y = y + dy[i]
                if ok(X, Y, W, H):
                    if m1[X][Y] == '#':
                        ret[x][y] = '#'
    return ret


def p(M):
    for l in M:
        print(l)


m1 = copy.deepcopy(L)
cnt = 0
while check(m1) == False:
    tmp = copy.deepcopy(m1)
    m1 = f(tmp)
    cnt += 1

print(cnt)


### FIXED CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

H, W = [int(x) for x in input().split()]
A = []
BQ = deque()
for _ in range(H):
    L = list(input())
    A.append(L)

bCnt = 0
for x in range(W):
    for y in range(H):
        if A[y][x] == '#':
            BQ.append((x, y))
            bCnt += 1


def check(a):
    a2 = sum(a, [])
    cnt = a2.count('.')
    return cnt == 0


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False


# X,Y座標
DX = [1, -1, 0, 0]
DY = [0, 0, 1, -1]

cnt = 0

while bCnt != H * W:
    newBQ = deque()
    for (x, y) in BQ:
        for (dx, dy) in zip(DX, DY):
            X = x + dx
            Y = y + dy
            if ok(X, Y, W, H) and A[Y][X] == '.':
                A[Y][X] = '#'
                newBQ.append((X, Y))
                bCnt += 1

    cnt += 1

    # print("len:{}".format(len(newBQ)))
    # for a in A:
    #     print(a)
    # print("---")

    BQ = newBQ

print(cnt)
### BUGGY CODE ###

#!/usr/bin/python
# coding: UTF-8

def main():
    A,B,M = list(map(int, input().split(' ')))

    a_list = list(map(int, input().split(' ')))
    b_list = list(map(int, input().split(' ')))

    dic = {}
    for i in range(A):
        dic[i]={}
    for i in range(A):
        for j in range(B):
            dic[i][j] = 0


    x_y_c_list = []

    for i in range(M):
        temp = list(map(int, input().split(' ')))
        x_y_c_list.append(temp)

        if dic[temp[0]-1][temp[1]-1] == 0:
            dic[temp[0]-1][temp[1]-1] = temp[2]
        else:
            if dic[temp[0]-1][temp[1]-1] < temp[2]:
                dic[temp[0]-1][temp[1]-1] = temp[2]

    price_list = -1
    for i in range(A):
        for j in range(B):
            if price_list == -1:
                price_list = a_list[i]+b_list[j] - dic[i][j]
            elif price_list > a_list[i]+b_list[j] - dic[i][j]:
                price_list = a_list[i]+b_list[j] - dic[i][j]
            else:
                price_list = price_list
            #price_list.append(a_list[i]+b_list[j] - dic[i][j])

    print(price_list)

if __name__=='__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python
# coding: UTF-8

def main():
    A,B,M = list(map(int, input().split(' ')))

    a_list = list(map(int, input().split(' ')))
    b_list = list(map(int, input().split(' ')))


    price_list = 2*10**5
    for i in range(M):
        temp = list(map(int, input().split(' ')))
        if price_list > a_list[temp[0]-1] + b_list[temp[1]-1] - temp[2]:
            price_list = a_list[temp[0]-1] + b_list[temp[1]-1] - temp[2]

    lower = min(a_list) + min(b_list)
    if lower < price_list:
        print(lower)
    else:
        print(price_list)

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

n=int(input())
a=[int(i) for i in input().split()]
amax=max(a)
m=len( bin(amax)[2:] )
bin_a = [bin(aa)[2:].zfill(m) for aa in a]

ans=0
mod=10**9+7
for i in range(m):
    sum0 = sum( bi[-1-i]=="0" for bi in bin_a )
    sum1 = sum( bi[-1-i]=="1" for bi in bin_a )
    ans += sum0*sum1*2**i % mod
print(ans%mod)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
amax=max(a)
m=len( bin(amax)[2:] )
bin_a = [bin(aa)[2:].zfill(m) for aa in a]

ans=0
mod=10**9+7
for i in range(m):
    sum0 = sum( bi[-1-i]=="0" for bi in bin_a )
    sum1 = n-sum0
    ans += sum0*sum1*2**i % mod
print(ans%mod)
### BUGGY CODE ###

n=int(input())
lis=list(map(int,input().split()))
x=1
for i in range(n):
  x*=lis[i]
if x>10**18:
  print(-1)
else :
  print(x)
  

### FIXED CODE ###

import sys
n=int(input())
lis=list(map(int,input().split()))
if 0 in lis :
  print(0)
  sys.exit()
x=1
for i in range(n):
  x*=lis[i]
  if  x>10**18:
    print(-1)
    sys.exit()
print(x)
### BUGGY CODE ###

import sys
L,R = map(int,input().split())
mod = 2019
cnt = 0
ans = float('inf')
List = [False for i in range(2019)]
for i in range(L,R):
    for j in range(i+1,R+1):
        tmp = (i*j)%mod
        List[tmp] = True
        ans = min(tmp,L*R,ans)
        if all(List):
            print(ans)
            sys.exit()
print(ans)

### FIXED CODE ###

import sys
L,R = map(int,input().split())
mod = 2019
cnt = 0
ans = float('inf')
List = [False for i in range(2019)]
for i in range(L,R):
    for j in range(i+1,R+1):
        tmp = (i*j)%mod
        List[tmp] = True
        ans = min(tmp,L*R,ans)
        if cnt>=10**6 or all(List)==True:
            print(ans)
            sys.exit()
        cnt +=1
print(ans)
### BUGGY CODE ###

#n = int(input())
#s = input()
n,x = map(int,input().split())
da = list(map(int,input().split()))
m = 100010
mod = 1000000007

dp = [0 for i in range(m)]
da.sort()
da.reverse()
dp[x] = 1
for i in range(n):
    for j in range(m):
        if j >= da[i]:
            dp[j%da[i]] += dp[j]
            dp[j] *= n-i-1
            if dp[j] >= mod: dp[j] %= mod
            if dp[j%da[i]] >= mod: dp[j] %= mod
        else:
            dp[j] *= n-i
            if dp[j] >= mod: dp[j]%=mod
ans = 0
for i in range(m):
    ans += dp[i] * i
    if ans >= mod: ans %= mod
print(ans)


### FIXED CODE ###

#n = int(input())
#s = input()
n,x = map(int,input().split())
da = list(map(int,input().split()))
m = 100010
mod = 1000000007

dp = [0 for i in range(m)]
da.sort()
da.reverse()
dp[x] = 1
for i in range(n):
    for j in range(m):
        if j >= da[i]:
            dp[j%da[i]] += dp[j]
            dp[j] *= n-i-1
            if dp[j] >= mod: dp[j] %= mod
            if dp[j%da[i]] >= mod: dp[j] %= mod
        else:
            dp[j] *= n-i
            if dp[j] >= mod: dp[j]%=mod
ans = 0
for i in range(m):
    ans += dp[i] * i
    if ans >= mod: ans %= mod
print(ans)
### BUGGY CODE ###

# しらんけど
n = int(input())
print(sum(range(n)))


### FIXED CODE ###

# しらんけど
# ふつうにこれやったらTLEなったのでアレする
# n = int(input())
# print(sum(range(n)))

n = int(input())
if n % 2 == 0:
    a = (1 + n) * (n // 2)
    print(a - n)
else:
    a = (1 + n) * ((n - 1) // 2) + (n // 2 + 1)
    print(a - n)
### BUGGY CODE ###

s = input()
counter = 0

while s.count('BW'):
  counter += s.count('BW')
  s = s.replace('BW', 'WB')
  
print(counter)

### FIXED CODE ###

s=input()

b_count = 0
ans = 0

for s_i in s:
  if s_i=='W':
    ans += b_count
  elif s_i=='B':
    b_count += 1

print(ans)
### BUGGY CODE ###

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

for i in range(N):
    for j in range(N):
        if A[j]==i+1:
            print(j+1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
li=[0]*n
for i in range(n):
  li[a[i]-1] += i+1
for i in range(n):
  li[i]=str(li[i])
print(" ".join(li))
### BUGGY CODE ###

N = int(input())

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

cnt = 0
t = []

for l in range(N):
  r = l + 1
  while r < N and H[r-1] >= H[r]:
    cnt += 1
    r += 1
  t.append(cnt)
  cnt = 0

print(max(t))

  

### FIXED CODE ###

N = int(input())

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

H = H[::-1]

l = 0
cnt = 0
t = 0

while l < N - 1:
  if H[l] <= H[l+1]:
    cnt += 1
  else:
    t = max(t,cnt)
    cnt = 0
  l += 1

print(max(t,cnt))
### BUGGY CODE ###

import heapq
x,y,z,k = map(int,input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
al = [[[0 for i in range(z)] for j in range(y)] for jj in range(x)]

hq = []
heapq.heappush(hq,(-(a[0]+b[0]+c[0]),0,0,0))
for i in range(k):
    hqi,ai,bi,ci = heapq.heappop(hq)
    print(-hqi)
    if ai+1 < x and al[ai+1][bi][ci] == 0:
        heapq.heappush(hq,(-(a[ai+1]+b[bi]+c[ci]),ai+1,bi,ci))
        al[ai+1][bi][ci] = -1
    if bi+1 < y and al[ai][bi+1][ci] == 0:
        heapq.heappush(hq,(-(a[ai]+b[bi+1]+c[ci]),ai,bi+1,ci))
        al[ai][bi+1][ci] = -1
    if ci+1 < z and al[ai][bi][ci+1] == 0:
        heapq.heappush(hq,(-(a[ai]+b[bi]+c[ci+1]),ai,bi,ci+1))
        al[ai][bi][ci+1] = -1


### FIXED CODE ###

import heapq
x,y,z,k = map(int,input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
al = []

hq = []
heapq.heappush(hq,(-(a[0]+b[0]+c[0]),0,0,0))
for i in range(k):
    hqi,ai,bi,ci = heapq.heappop(hq)
    print(-hqi)
    if ai+1 < x and not (ai+1,bi,ci) in al:
        heapq.heappush(hq,(-(a[ai+1]+b[bi]+c[ci]),ai+1,bi,ci))
        al.append((ai+1,bi,ci))
    if bi+1 < y and not (ai,bi+1,ci) in al:
        heapq.heappush(hq,(-(a[ai]+b[bi+1]+c[ci]),ai,bi+1,ci))
        al.append((ai,bi+1,ci))
    if ci+1 < z and not (ai,bi,ci+1) in al:
        heapq.heappush(hq,(-(a[ai]+b[bi]+c[ci+1]),ai,bi,ci+1))
        al.append((ai,bi,ci+1))
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
    A[N-1]=A[N-1]//2
    if A[N-2]>A[N-1]:
        A.sort()
    if A[N-1]==0:
        break
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=[-1*int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
    a=-1*heapq.heappop(A)
    a=a//2
    heapq.heappush(A,-1*a)
print(-1*sum(A))
### BUGGY CODE ###

def main():
    k, s = map(int, input().split())
    cnt = 0
    for x in range(k+1):
        for y in range(k+1):
            for z in range(k+1):
                if x+y+z == s: cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    k, s = map(int, input().split())
    cnt = 0
    for x in range(k+1):
        for y in range(k+1):
            if 0 <= s-x-y and s-x-y <= k: cnt += 1
    print(cnt)


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

import sys
sys.setrecursionlimit(10**9)

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

memo = [[float('inf')]*410 for _ in range(410)]
visit = [[False]*410 for _ in range(410)]

from itertools import accumulate
B = [0]+A
B = list(accumulate(B))

def dp(l, r):
  if l == r:
    return 0
  if visit[l][r]:
    return memo[l][r]
  visit[l][r] = True
  res = float('inf')
  for c in range(l, r):
    res = min(res, dp(l, c)+dp(c+1, r)+B[r+1]-B[l])
  memo[l][r] = res
  return res

print(dp(0, n-1))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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

memo = [[float('inf')]*410 for _ in range(410)]
visit = [[False]*410 for _ in range(410)]

from itertools import accumulate
B = [0]+A
B = list(accumulate(B))

def dp(l, r):
  if l == r:
    return 0
  if visit[l][r]:
    return memo[l][r]
  visit[l][r] = True
  res = float('inf')
  for c in range(l, r):
    res = min(res, dp(l, c)+dp(c+1, r)+B[r+1]-B[l])
  memo[l][r] = res
  return res

print(dp(0, n-1))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

def don(dk, rate, amin):
    if not rate:
        return dk
    if len(rate)==1:
        a,b=rate[0]
        p,m=divmod(dk,a)
        return p*b+m
    if dk < amin:
        return dk
    if dp[dk] != -1:
        return dp[dk]
    mx = 0
    for a, b in rate:
        if a > dk: continue
        tmp = don(dk - a, rate, amin) + b
        if tmp > mx:
            mx = tmp
    dp[dk] = mx
    return mx

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
atob = []
btoa = []
amin = 10 ** 7
bmin = 10 ** 7
for a, b in zip(aa, bb):
    if a < b:
        atob.append([a, b])
        if a < amin:
            amin = a
    elif a > b:
        btoa.append([b, a])
        if b < bmin:
            bmin = b
dp = [-1] * (n + 1)
n = don(n, atob, amin)
dp = [-1] * (n + 1)
print(don(n, btoa, bmin))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

def don(dk, rate, amin):
    if not rate:
        return dk
    if len(rate)==1:
        a,b=rate[0]
        p,m=divmod(dk,a)
        return p*b+m
    if len(rate)==2:
        a0,b0=rate[0]
        a1,b1=rate[1]
        if b0/a0<b1/a1:
            a0,b0,a1,b1=a1,b1,a0,b0
        p0,m=divmod(dk,a0)
        re=b0*p0
        p1,m=divmod(m,a1)
        re+=b1*p1+m
        while p0>0 and m>0:
            p0-=1
            m+=a0
            p2,m=divmod(m,a1)
            p1+=p2
            tmp=p0*b0+p1*b1+m
            if tmp>re:
                re=tmp
        return re
    if dk < amin:
        return dk
    if dp[dk] != -1:
        return dp[dk]
    mx = 0
    for a, b in rate:
        if a > dk: continue
        tmp = don(dk - a, rate, amin) + b
        if tmp > mx:
            mx = tmp
    dp[dk] = mx
    return mx

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
atob = []
btoa = []
amin = 10 ** 7
bmin = 10 ** 7
for a, b in zip(aa, bb):
    if a < b:
        atob.append([a, b])
        if a < amin:
            amin = a
    elif a > b:
        btoa.append([b, a])
        if b < bmin:
            bmin = b
dp = [-1] * (n + 1)
n = don(n, atob, amin)
dp = [-1] * (n + 1)
print(don(n, btoa, bmin))