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

from collections import deque

N = int(input())
M = N - 1
graph = [[] for _ in range(N + 1)]
dis_f = []
dis_s = []
#フェネックの距離
for i in range(M):
    a,b = map(int,input().rstrip().split(" "))
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (N + 1)
dist[0] = 0
dist[1] = 0
d = deque()
d.append(1)
while(d):
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)
    ans_f = dist[1:]
    
#すぬけくんの距離

dist = [-1] * (N + 1)
dist[0] = 0
dist[N] = 0
d = deque()
d.append(N)
while(d):
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)
    ans_s = dist[1:]

count_f = 0
count_s = 0
for i in range(N):
    if(ans_f[i] <= ans_s[i]):
        count_f += 1
    else:
        count_s += 1
if(count_f > count_s):
    print("Fennec")
else:
    print("Snuke")

### FIXED CODE ###

from collections import deque

N = int(input())
M = N - 1
graph = [[] for _ in range(N + 1)]
dis_f = []
dis_s = []
#フェネックの距離
for i in range(M):
    a,b = map(int,input().rstrip().split(" "))
    graph[a].append(b)
    graph[b].append(a)

dist_f = [-1] * (N + 1)
dist_f[0] = 0
dist_f[1] = 0
d = deque()
d.append(1)
left = N -1
while(d):
    v = d.popleft()
    for i in graph[v]:
        if dist_f[i] != -1:
            continue
        dist_f[i] = dist_f[v] + 1
        d.append(i)
    
#すぬけくんの距離

dist = [-1] * (N + 1)
dist[0] = 0
dist[N] = 0
d = deque()
d.append(N)
while(d):
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)

count_f = 0
count_s = 0
for i in range(N):
    if(dist_f[i + 1] <= dist[i + 1]):
        count_f += 1
    else:
        count_s += 1
if(count_f > count_s):
    print("Fennec")
else:
    print("Snuke")
### BUGGY CODE ###

n, q = map(int, input().split())
S = list(input())

lr = []
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])

for temp in lr:
    l, r = temp
    string = S[l-1:r]

    cnt = 0
    for i in range(len(string)-1):
        if string[i] == "A" and string[i+1] == "C":
            cnt += 1
    print(cnt)

### FIXED CODE ###

n, q = map(int, input().split())
S = list(input())

lr = []
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])

t = [0] * (n+1)
for i in range(n-1):
    if S[i] == "A" and S[i+1] == "C":
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

for temp in lr:
    l, r = temp
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

N = int(input())
S = input()
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    for i in range(1,n):
        if i <= LCP[i]:
            LCP[i] = i
    return LCP
ans = 0
for i in range(N):
    T = S[i:]
    R = Z_algo(T)
    R.pop(0)
    R.append(0)
    ans = max(max(R),ans)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    for i in range(1,n):
        if i <= LCP[i]:
            LCP[i] = i
    return LCP
ans = 0
for i in range(N):
    T = S[i:]
    R = Z_algo(T)
    R.pop(0)
    R.append(0)
    ans = max(max(R),ans)
print(ans)
### BUGGY CODE ###

import itertools
s=input()
t=input()
tmp=False
if len(s)<len(t):
  tmp=True
s,t=sorted(list(s))[:min(len(s),len(t))],sorted(list(t))[-min(len(s),len(t)):]

slist=list(itertools.permutations(s,len(s)))
tlist=list(itertools.permutations(t,len(t)))

S="".join(sorted(slist)[0])
T="".join(sorted(tlist)[-1])
if S<T:
  print("Yes")
elif S==T and tmp:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import itertools
s=input()
t=input()
S="".join(sorted(list(s)))
T="".join(sorted(list(t)))[::-1]
if S<T:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

from itertools import accumulate

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0] * (K+1)
dp[K] = 1
for a in A:
    temp = [0] * (K+1)
    for k in range(K+1):
        temp[k - min(a, k)] += dp[k]; temp[k - min(a, k)] %= MOD
        temp[k] -= dp[k]; temp[k] %= MOD
    temp = list(accumulate(temp))
    dp = [(d + t) % MOD for d, t in zip(dp, temp)]
print(dp[0] % MOD)

### FIXED CODE ###

from itertools import accumulate

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0] * (K+1)
dp[K] = 1
for a in A:
    temp = [0] * (K+1)
    for k in range(K+1):
        temp[k - min(a, k)] += dp[k]; temp[k - min(a, k)] %= MOD
        temp[k] -= dp[k]; temp[k] %= MOD
    temp = list(accumulate(temp))
    dp = [(d + t) % MOD for d, t in zip(dp, temp)]
print(dp[0] % MOD)
### BUGGY CODE ###

l,r=map(int,input().split())
g = list([i%2019 for i in range(l,r+1)])
m=[]
for i in range(len(g)-1):
    for j in range(i+1,len(g)):
        m.append(g[i]*g[j]%2019)
        if g[i]*g[j]%2019 == 0:
            print(0)
            exit()
print(min(m))

### FIXED CODE ###

l,r=map(int,input().split())
if r - l >= 2019:
    print(0)
    exit()
g = list([i%2019 for i in range(l,r+1)])
m=[]
for i in range(len(g)-1):
    for j in range(i+1,len(g)):
        m.append(g[i]*g[j]%2019)
print(min(m))
### BUGGY CODE ###

N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[-1]*(W+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  for j in range(W+1):
    dp[i][j] = max(dp[i][j], dp[i-1][j])
    if -1 < j-weight[i]:
      dp[i][j] = max(dp[i][j], dp[i-1][j-weight[i]]+ value[i])
print(max(dp[N]))

### FIXED CODE ###

N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[-1]*(W+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  for j in range(W+1):
    dp[i][j] = max(dp[i][j], dp[i-1][j])
    if -1 < j-weight[i]:
      dp[i][j] = max(dp[i][j], dp[i-1][j-weight[i]]+ value[i])
print(max(dp[N]))
### BUGGY CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [INF] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j == n:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[-1])


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [INF] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j == n:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[-1])
### BUGGY CODE ###

kazu = int(input())
word = input()
score = word.split()
scin = [0]*kazu
zero = 0
for i in range(kazu):
    scin[i] = int(score[i])
    if scin[i] == 0:
        zero = 1

answer = 1
for j in range(kazu):
    answer *= scin[j]
    if answer > 10**18 and zero == 0:
        answer = -1

if zero == 1 and answer > 10**18:
    answer = -1

print(answer)

### FIXED CODE ###

kazu = int(input())
word = input()
score = word.split()

maxn = 10**18
zero = 0
answer = 1
scin = [0]*kazu

for i in range(kazu):
    scin[i] = int(score[i])
    if scin[i] == 0:
        zero = 1
if zero == 1:
    answer = 0
else:
    for j in range(kazu):
        answer *= scin[j]
        if answer > maxn:
            answer = -1
            break
print(answer)
### BUGGY CODE ###

sn,bn=map(int,input().split(" "))
fu=[int(sn*(sn-1)/2)]
gr_si=[n for n in range(sn+1)]
siL_gr=[[n] for n in range(sn+1)]
siL_br=[]
for _ in range(bn):
    siL_br.append(list(map(int, input().split(" "))))
siL_br=siL_br[::-1]

for bri in range(bn-1):
    si1,si2=siL_br[bri]
    gr1 = gr_si[si1]
    gr2 = gr_si[si2]
    if gr1==gr2:
        fu.append(fu[bri])
    else:
        lengr1 = len(siL_gr[gr1])
        lengr2 = len(siL_gr[gr2])
#        if lengr1<lengr2:
#            gr1,gr2=gr2,gr1
        fu.append(fu[bri]-lengr1*lengr2)
        for si in siL_gr[gr2]:
            gr_si[si]=gr1
        siL_gr[gr1]+=siL_gr[gr2]
        siL_gr[gr2]=[]

print(*fu[::-1],sep="\n")


### FIXED CODE ###

sn,bn=map(int,input().split(" "))
fu=[int(sn*(sn-1)/2)]
gr_si=[n for n in range(sn+1)]
siL_gr=[[n] for n in range(sn+1)]
siL_br=[]
for _ in range(bn):
    siL_br.append(list(map(int, input().split(" "))))
siL_br=siL_br[::-1]

for bri in range(bn-1):
    si1,si2=siL_br[bri]
    gr1 = gr_si[si1]
    gr2 = gr_si[si2]
    if gr1==gr2:
        fu.append(fu[bri])
    else:
        lengr1 = len(siL_gr[gr1])
        lengr2 = len(siL_gr[gr2])
        if lengr1<lengr2:
            gr1,gr2=gr2,gr1
        fu.append(fu[bri]-lengr1*lengr2)
        for si in siL_gr[gr2]:
            gr_si[si]=gr1
        siL_gr[gr1]+=siL_gr[gr2]
        siL_gr[gr2]=[]

print(*fu[::-1],sep="\n")
### BUGGY CODE ###


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


# def init(n_):
#     #簡単にするために2のべき乗に揃える
#     n = 1
#     while n <= n_:
#         n *= 2
#     return n

#初期化
N = int(input())
n = 1
while n <= N:
    n *= 2

data = [0] * (2 * n - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0
for i in range(N):
    # h = int(input())
    # a = int(input())
    h = H[i]
    a = A[i]
    # tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(h, query(1, h + 1) + a)
    # ans = max(ans, tmp + a)
    # print (data)

print (query(1, N + 1))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

# 操作回数を入力する
N = int(input())
# 言う数字を入力する
list_A = [int(input()) for _ in range(N)]
# 終了後に残っている数字の数を設定する
ans = 0
# list_A内の数字Aについて操作を繰り返す
while list_A != []:
    A = list_A[0]
    # Aが言われる回数を求める
    count = list_A.count(A)
    # 奇数回言われる場合、ansを増やす
    if count % 2 != 0:
        ans += 1
    # list_AからAを全て削除する
    for _ in range(count):
        list_A.remove(A)
#結果を返す
print(ans)

### FIXED CODE ###

import bisect
# 操作回数を入力する
N = int(input())
# 言う数字を入力する
list_A = [int(input()) for _ in range(N)]
# 紙の状態を設定する
paper = []
# 
for A in list_A:
    if paper == []:
        paper.append(A)
        continue
    # 紙上のAをニ分探索する
    index = bisect.bisect_left(paper, A)
    if index < len(paper) and paper[index] == A:
        del paper[index]
    else:
        paper.insert(index, A)
# 結果を出力する
print(len(paper))
### BUGGY CODE ###

N, W = map(int, input().split())
items = [[0, 0]]
for _ in range(N):
    items.append(list(map(int, input().split())))

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(W + 1):
        if j - items[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j - items[i][0]] + items[i][1], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(dp[N]))

### FIXED CODE ###

N, W = map(int, input().split())
items = [[0, 0]]
for _ in range(N):
    items.append(list(map(int, input().split())))

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(W + 1):
        if j - items[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j - items[i][0]] + items[i][1], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(dp[N]))
### BUGGY CODE ###

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

dp=[100000 for i in range(N)]
dp[0]=0

for i in range(1,N):
    x=min(K,i)
    dp[i]=min([dp[i-k]+abs(h[i]-h[i-k]) for k in range(1,1+x)])

print(dp[N-1])

### FIXED CODE ###

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

dp=[100000 for i in range(N)]
dp[0]=0

for i,h_now in enumerate(h):
    if i==0:
        continue
    x=max(0,i-K)
    dp[i]=min([dp_i+abs(h_now-h_i) for dp_i,h_i in zip(dp[x:i],h[x:i])])

print(dp[N-1])
### BUGGY CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*(lk+1) for _ in range(ls)] for i in range(ls)]
  for i in range(ls):
    dp[i][i][0] = 1
  for k in range(lk+1):
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        if s[i] == s[j]:
          dp[i][j][k] = dp[i+1][j-1][k] + 2
        elif k:
          dp[i][j][k] = dp[i+1][j-1][k-1] + 2
        dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][k], dp[i][j-1][k])

  print(max(dp[0][ls-1]))
  return

solve()

### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()
### BUGGY CODE ###

import sys
import copy

def solve():
    N,Q=map(int,input().split())
    s=list(map(lambda e:ord(e)-65,list(input())))
    s2=[[] for i in range(26)]
    for i,c in enumerate(s):
        s2[c].append(i+1)
    r2=copy.copy(s2)
    for i in range(26):
        r2[i]=list(reversed(r2[i]))

    m=[1 for i in range(N+2)]
    m[0]=0
    m[N+1]=0

    #print()
    #print(s2)
    #print(r2)
    #print(0,0,s)
    #print(0,0,m)
    for i in range(Q,0,-1):
        t,d=sys.stdin.readline().rstrip().split()
        t=ord(t)-65
        if d=='L':
            for j in s2[t]:
                if m[j] != 0:
                    m[j-1]+=m[j]
                    m[j]=0
            #if i & 0xff == 0:
            #    s2[t]=[e for e in s2[t] if e <= i or e >= N-i]
        else:
            for j in r2[t]:
                if m[j] != 0:
                    m[j+1]+=m[j]
                    m[j]=0
            #if i & 0xff == 0:
            #    r2[t]=[e for e in r2[t] if e <= i or e >= N-i]
        #print(t,d,m)
    return N-m[0]-m[N+1]

print(solve())


### FIXED CODE ###

import sys

N,Q=map(int,input().split())
s=[-1]
s+=list(map(lambda e:ord(e)-65,list(input())))
s+=[-1]
t=[]
d=[]
for i in range(Q):
    ti,di=sys.stdin.readline().rstrip().split()
    ti=ord(ti)-65
    di = -1 if di=='L' else +1
    t.append(ti)
    d.append(di)

def solve(n):
    for i in range(Q):
        if s[n]==t[i]:
            n+=d[i]
    return n

def find_match(x):
    f1 = 1
    f2 = N + 1
    while f1 != f2:
        f3 = (f1 + f2) // 2
        if solve(f3) == x:
            f1 = f3 + 1
        else:
            f2 = f3
    return f1

def find_notmatch(x):
    f1 = 1
    f2 = N + 1
    while f1 != f2:
        f3 = (f1 + f2) // 2
        #print(f1,f2,f3,solve(f3),x)
        if solve(f3) != x:
            f1 = f3 + 1
        else:
            f2 = f3
    return f1

#for i in range(1,N+1):
#    print(solve(i))

print(find_notmatch(N+1)-find_match(0))
### BUGGY CODE ###

N, K = map(int, input().split())
array = []

for i in range(N):
  a, b = map(int, input().split())
  for j in range(b):
    array.append(a)
    
array.sort()

print(array[K- 1])

### FIXED CODE ###

N, K = map(int, input().split())
array = [0]*(10**5+ 1)

for i in range(N):
  a, b = map(int, input().split())
  array[a]+= b
  
S = 0
i = 0

while S < K:
  S+= array[i]
  i+= 1
  
print(i- 1)
### BUGGY CODE ###

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

res = 0
for i in range(N):
  for j in range(i+1, N):
    for k in range(j+1, N):
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        if (j-i) != (k-j):
          res += 1

print(res)

### FIXED CODE ###

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

r, g, b = 0, 0, 0
for c in S:
  if c == "R": r += 1
  if c == "G": g += 1
  if c == "B": b += 1

total = r*g*b

for i in range(N):
  for j in range(i+1, N):
    if S[i] == S[j]: continue

    k = 2*j - i
    if k >= N: continue
    if S[i] == S[k] or S[j] == S[k]: continue
    total -= 1

print(total)
### BUGGY CODE ###

N, W = [int(i) for i in input().split()]
weight, value = [0] * N, [0] * N
for i in range(N):
    weight[i], value[i] = [int(i) for i in input().split()]

dp = [[0] * (W+1) for _ in range(N)]
dp[0][weight[0]] = value[0]
for i in range(1, N):
    for w in range(W+1):
        if w-weight[i] >= 0:
            dp[i][w] = max(dp[i-1][w-weight[i]]+value[i], dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]
print(max(dp[N-1]))

### FIXED CODE ###

N, W = [int(i) for i in input().split()]
weight, value = [0] * N, [0] * N
for i in range(N):
    weight[i], value[i] = [int(i) for i in input().split()]

dp = [[0] * (W+1) for _ in range(N)]
dp[0][weight[0]] = value[0]
for i in range(1, N):
    for w in range(W+1):
        if w-weight[i] >= 0:
            dp[i][w] = max(dp[i-1][w-weight[i]]+value[i], dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]
print(max(dp[N-1]))
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
li = list(int(stdin.readline().rstrip()) for _ in range(n))
li_to = sorted(li)
one = li_to[-1]
two = li_to[-2]
for i in range(n):
    if max(li) != li[i]:
        print(one)
    else:
        print(two)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a_m = max(a)
a_i = a.index(a_m)
a.sort()
for i in range(len(a)):
  if i == a_i:
    print(a[-2])
  else:
    print(a_m)
### BUGGY CODE ###

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

import math

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

count = 0
for a in A:
    for b in B:
        if a >= b:
            continue
        for c in C:
            if b >= c:
                continue
            count += 1

print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import bisect
 
n = int(input())
 
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
B.sort()
C.sort()
 
Ac, Cc = [0]*n, [0]*n
# Ap, Cp = 0, 0
 
for i in range(n):
    Ac[i] = bisect.bisect_left(A, B[i])#[Ap:], B[i])
    # Ac[i], Ap = index + Ap, index + Ap
    Cc[i] = n - bisect.bisect_right(C, B[i])#[Cp:], B[i])
    # Cc[i], Cp = n - index - Cp, index + Cp
 
 
count = 0
for i in range(n):
    count += Ac[i]*Cc[i]
 
print(count)
### BUGGY CODE ###

from collections import deque
S =input()
counter = 0
S = list(S)
q = deque([])
for i in range(len(S)):
    q.append(S[i])
for i in range(10000000):
    if q:
        s1 = q.pop()
    else:
        break
    if q:
        s2 = q.pop()
    else:
        break
    if(s1 != s2):
        counter+=2
    else:
        q.appendleft(s1)
        q.append(s2)
print(counter)

### FIXED CODE ###

S =input()
S = list(S)
c_one = S.count('1')
c_zero = S.count('0')
print(min(c_one,c_zero)*2)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
a=True
for i in range(n):
  for j in range(i,n):
    if h[i]-h[j]>1:
      a=False
if a==False:
  print('No')
else:
  print('Yes')


### FIXED CODE ###

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

for i in range(n-1):
  if h[i]<h[i+1]:
    h[i+1]-=1
if sorted(h)==h:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import collections
n, m =map(int,input().split())
p = []
for i in range(m):
    p.append(input().split())

del_l = []
for j in range(m):
    if p[j][1] == 'AC':
        del_l.append(p[j][0])
        p[j][0] = 'pass'
        p[j][1] = 'pass'
    if p[j][1] =='WA' and p[j][0] in del_l:
        p[j][0] = 'pass'
        p[j][1] = 'pass'
pen = 0
for s in range(m):
    if p[s][1] == 'WA' and p[s][0] in del_l:
        pen += 1
print(len(collections.Counter(del_l)),pen)

### FIXED CODE ###

n, m = map(int,input().split())
a = [input().split() for i in range(m)]
p = [int(i[0]) for i in a]
q = [j[1] for j in a]

ac = 0
wa = 0
wa_c = [0] * n
ac_c = [False] * n

for t in range(m):
    if ac_c[p[t]-1]:
        continue
    if q[t] == 'AC':
        ac += 1
        ac_c[p[t]-1] = True
        wa += wa_c[p[t]-1]
    else:
        wa_c[p[t]-1] += 1
print(ac,wa)
### BUGGY CODE ###

N,K = map(int, input().split())
N += 1 ; K += 1
H = list(map(int, input().split()))
L = [0] + [1000000000]*N
for i in range (N):
  for j in range(i+1, min(i+K, N-1)):
    L[j] = min(L[j], L[i] + abs(H[j] - H[i]))
print(L[N-2])

### FIXED CODE ###

N,K = map(int, input().split())
H = list(map(int, input().split()))
L = [0]*N
for i in range (1,N):
  L[i] = min(L[i-j] + abs(H[i] - H[i-j]) for j in range(1, min(i,K)+1))
print(L[N-1])