Harryxun/stf_run huggingface dataset:
import sys


def dep(u, p):
    D[u] = p
    if tree[u][2] != NIL:
        dep(tree[u][2], p)
    if tree[u][1] != NIL:
        dep(tree[u][1], p+1)


def print_ans():
    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i],
                      "root" if tree[i][0] == NIL else "leaf" if tree[i][1] == NIL else "internal node",
                      tree[i][3]))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    root = set(range(n))
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        tree[a[0]].append(a[2:])
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
        root -= set(a[2:])
    dep(root.pop(), 0)
    print_ans()

### FIXED CODE ###

import sys


def dep(u, p):
    D[u] = p
    for i in tree[u][3]:
        dep(i, p+1)


def print_ans():
    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i],
                      "root" if tree[i][0] == NIL else "leaf" if tree[i][1] == NIL else "internal node",
                      tree[i][3]))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    root = set(range(n))
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        tree[a[0]].append(a[2:])
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
        root -= set(a[2:])
    dep(root.pop(), 0)
    print_ans()
class BTree:
    def __init__(self):
        self.value = None
        self.left = None
        self.right = None

    def insert(self, s):
        if self.value is None:
            self.value = s
        else:
            if self.value < s:
                if self.right is None:
                    self.right = BTree().insert(s)
                else:
                    self.right = self.right.insert(s)
            elif s < self.value:
                if self.left is None:
                    self.left = BTree().insert(s)
                else:
                    self.left = self.left.insert(s)
        return self

    def find(self, s):
        if self.value == s:
            return True
        elif self.value < s:
            if self.right is None:
                return False
            else:
                return self.right.find(s)
        else:
            if self.left is None:
                return False
            else:
                return self.left.find(s)


n = int(input())
tree = BTree()
for _ in range(n):
    command = input().split()
    if command[0] == "insert":
        tree = tree.insert(command[1])
    elif command[0] == "find":
        if tree.find(command[1]):
            print("yes")
        else:
            print("no")


### FIXED CODE ###

n = int(input())
data = set()
for _ in range(n):
    command = input().split()
    if command[0] == "insert":
        data.add(command[1])
    elif command[0] == "find":
        if command[1] in data:
            print("yes")
        else:
            print("no")
n = int(input())
s = input()


for i in s:
    m = (ord(i) - ord('A') + n) % 26
    ans += chr(m + ord('A'))

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = str()
for i in S:
	m = (ord(i) - ord('A') + N) % 26
	ans += chr(m + ord('A'))
print(ans)
n=int(input())
def factorization(n):
  primen = []
  degree = []
  primend = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      primen.append(i)
      degree.append(cnt)
      primend.append([i,cnt])
  if temp!=1:
    primen.append(temp)
    degree.append(1)
    primend.append([temp,1])
  if primen==[]:
    primen.append(n)
    degree.append(1)
    primend.append([n,1])
  return primend#primen,degree
pn=[0]*(n+1)
for i in range(1,n+1):
  for j in factorization(i):
    pn[j[0]]+=j[1]
ans = 1
for k in range(2,n+1):
  ans*=(pn[k]+1)%(10**9+7)
print(pn%(10**9+7))

### FIXED CODE ###

n=int(input())
def factorization(n):
  primen = []
  degree = []
  primend = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      primen.append(i)
      degree.append(cnt)
      primend.append([i,cnt])
  if temp!=1:
    primen.append(temp)
    degree.append(1)
    primend.append([temp,1])
  if primen==[]:
    primen.append(n)
    degree.append(1)
    primend.append([n,1])
  return primend#primen,degree
pn=[0]*(n+1)
for i in range(1,n+1):
  for j in factorization(i):
    pn[j[0]]+=j[1]
ans = 1
for k in range(2,n+1):
  ans*=(pn[k]+1)%(10**9+7)
print(ans%(10**9+7))
n = int(input())
x = int(input())
t = int(input())
 
if(n%x==0):
  count,mod = divmod(n,x)
else:
  count,mod = divmod(n,x)
  count = count + 1
 
print(count*t)

### FIXED CODE ###

n = []
n = input().split()
n_1 = int(n[0])
x = int(n[1])
t = int(n[2])
 
if(n_1%x==0):
  count,mod = divmod(n_1,x)
else:
  count,mod = divmod(n_1,x)
  count = count + 1
 
print(count*t)
n,k = map(int,input().split())
a = list(map(int,input().split()))

len_a=len(str(bin(max(a))))-2
len_k=len(str(bin(k)))-2

if len_a >= len_k:
  length =len_a
  for i in range(n):
    a[i] = ("0"*length+str(bin(a[i]))[2:])[-len_a:] 
elif len_a < len_k:
  length =len_k
  for i in range(n):
    a[i] = ("0"*length+str(bin(a[i]))[2:])[-len_k:]
    
k = ("0"*length+str(bin(k))[2:])[-length:]

flag = False
for i in range(length):
  count_0 =0
  count_1 =0
  for j in range(n):
    if a[j][i]=="0":
      count_0 += 1
    else:
      count_1 += 1
  #print(count_0,count_1)
  if count_0 <= count_1 and k[i]=="1":
    if i==0:   
      k="0"+k[1:i]
    elif i == length - 1:
      k= k[0:i]+"0"
    else:
      k= k[0:i]+"0"+k[i+1:]
    flag = True
  elif count_0 > count_1 and k[i]=="0" and flag:
    if i==0:   
      k="1"+k[1:i]
    elif i == length - 1:
      k= k[0:i]+"1"
    else:
      k=k[0:i]+"1"+k[i+1:]
      
ans = 0
for i in range(n):
  for j in range(length):
    if a[i][j]!=k[j]:
      ans +=2**(length-1-j)
print(ans)

### FIXED CODE ###

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

len_a=len(str(bin(max(a))))-2
len_k=len(str(bin(k)))-2

if len_a >= len_k:
  length =len_a
  for i in range(n):
    a[i] = ("0"*length+str(bin(a[i]))[2:])[-len_a:] 
elif len_a < len_k:
  length =len_k
  for i in range(n):
    a[i] = ("0"*length+str(bin(a[i]))[2:])[-len_k:]
    
k = ("0"*length+str(bin(k))[2:])[-length:]

flag = False
for i in range(length):
  count_0 =0
  count_1 =0
  for j in range(n):
    if a[j][i]=="0":
      count_0 += 1
    else:
      count_1 += 1
  #print(count_0,count_1)
  if count_0 <= count_1 and k[i]=="1":
    if i==0:   
      k="0"+k[1:length]
    elif i == length - 1:
      k= k[0:i]+"0"
    else:
      k= k[0:i]+"0"+k[i+1:]
    flag = True
  elif count_0 > count_1 and k[i]=="0" and flag:
    if i==0:   
      k="1"+k[1:length]
    elif i == length - 1:
      k= k[0:i]+"1"
    else:
      k=k[0:i]+"1"+k[i+1:]
      
ans = 0
for i in range(n):
  for j in range(length):
    if a[i][j]!=k[j]:
      ans +=2**(length-1-j)
print(ans)
import math

def append_factors(n, f, p):
    num_factors = 0
    while n % p == 0:
        num_factors += 1
        n //= p
    if num_factors != 0:
        f[p] = num_factors
    return n

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    n = append_factors(n, ret, 2)
    n = append_factors(n, ret, 3)
    i = 6
    while i*i <= n + 1:
        p1, p2 = i - 1, i + 1
        n = append_factors(n, ret, i - 1)
        n = append_factors(n, ret, i + 1)
        i += 6
    if n != 1:
        append_factor(ret, n)

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n^2 < n(n+1) <= 2x < (n+1)(n+2) < (n+2)^2

    n = int(math.sqrt(x))
    while (n + 1)*(n + 2) <= 2*x:
        n += 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math

def append_factor(f, p):
    if p not in f:
        f[p] = 0
    f[p] += 1

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    while n % 2 == 0:
        append_factor(ret, 2)
        n //= 2
    while n % 3 == 0:
        append_factor(ret, 3)
        n //= 3
    for i in range(6, l, 6):
        while n % (i - 1) == 0:
            append_factor(ret, i - 1)
            n //= (i - 1)
        while n % (i + 1) == 0:
            append_factor(ret, i + 1)
            n //= (i + 1)
    if n != 1:
        append_factor(ret, n)

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n^2 < n(n+1) <= 2x < (n+1)(n+2) < (n+2)^2

    n = int(math.sqrt(x))
    while (n + 1)*(n + 2) <= 2*x:
        n += 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()
a, b, h = map(int, input().split())
print((a + b) * h // 2)


### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print((a + b) * h // 2)
def dfs(c, t, node, p=-1):
    for child in t[node]:
        if child==p:
            continue
        c[child] += c[node]
        c, t = dfs(c, t, child, node)
    return c, t

def main():
    n, q = map(int, input().split())
    t = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        t[a].append(b); t[b].append(a)
    c = [0]*n
    for i in range(q):
        p, x = map(int, input().split())
        p -= 1
        c[p] += x

    c, _ = dfs(c, t, 0)
    print(*c)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n

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

for i in range(q):
    p, x = map(int, input().split())
    node[p-1] += x

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)
a,b=map(int,input().split())
c=(b-c)
s=0
for i in range(1,c+1):
    s+=i
print(s-b)

### FIXED CODE ###

a,b=map(int,input().split())
c=(b-a)
s=0
for i in range(1,c+1):
    s+=i
print(s-b)
N = int(input())
X = [int(input()) for i in range(N)]
cnt = 0
lst = []
X.sort()
for i in range(N-1):
  if X[i] < X[i+1] :
    cnt += 1
  else:
    lst.append(cnt)
    cnt = 0
print(min(lst))
    

### FIXED CODE ###

N = int(input())

lst = []
for i in range(N):
  lst.append(int(input()))
print(len(set(lst)))
N= input()
for i in range 3:
  if N[i]=='7':
    print('Yes')
    exit()

print('No')

### FIXED CODE ###

N = input()
if N[0]!=('7') and N[1]!=('7') and N[2]!=('7'):
  print('No')
else:
  print('Yes')
def f(A, i, j, k, next,res):
    if A[i] == A[j] == 0:
        print("No")
        exit()
    elif A[i] == A[j] == 1 and A[k] == 0:
        if i in next:
            A[i] += 1
            A[j] -= 1
            return "ABC"[i]
        else:
            A[i] -= 1
            A[j] += 1
            return "ABC"[j]
    else:
        A[i] += 1
        A[j] -= 1
        return "ABC"[i]
    

def main():
    N, A, B, C = [int(_n) for _n in input().split()]
    S = []
    for i in range(N):
        s = input()
        S.append(s)
    if [A,B,C].count(0) == 3:
        print("No")
        return
    res = ""
    arr = [A,B,C]
    S.append("")
    for i,s in enumerate(S):
        if s == "AB":
            if arr[0] > arr[1]:
                res += f(arr, 1, 0, 2, S[i+1],res)
            else:
                res += f(arr,0,1,2,S[i+1],res)
        elif s == "BC":
            if arr[1] > arr[2]:
                res += f(arr, 2, 1, 0, S[i+1],res)
            else:
                res += f(arr,1,2,0,S[i+1],res)
        elif s == "AC":
            if arr[0] > arr[2]:
                res += f(arr, 0, 2, 1, S[i+1],res)
            else:
                res += f(arr,2,0,1,S[i+1],res)
    for s in res:
        print(s)
main()

### FIXED CODE ###

def f(A, i, j, k, nex,res):
    if A[i] == A[j] == 0:
        print("No")
        exit()
    elif A[i] == A[j] == 1 and A[k] == 0:
        if i in nex:
            A[i] += 1
            A[j] -= 1
            return "ABC"[i]
        else:
            A[i] -= 1
            A[j] += 1
            return "ABC"[j]
    else:
        A[i] += 1
        A[j] -= 1
        return "ABC"[i]
    

def main():
    N, A, B, C = [int(_n) for _n in input().split()]
    S = []
    for i in range(N):
        s = input()
        S.append(s)
    if [A,B,C].count(0) == 3:
        print("No")
        return
    res = ""
    arr = [A,B,C]
    S.append("")
    for i,s in enumerate(S[:-1]):
        n = []
        if S[i+1] == "AB":
            n = [0,1]
        if S[i+1] == "BC":
            n = [2,1]
        if S[i+1] == "AC":
            n = [0,2]
        if s == "AB":
            if arr[0] > arr[1]:
                res += f(arr, 1, 0, 2, n,res)
            else:
                res += f(arr,0,1,2,n,res)
        elif s == "BC":
            if arr[1] > arr[2]:
                res += f(arr, 2, 1, 0, n,res)
            else:
                res += f(arr,1,2,0,n,res)
        elif s == "AC":
            if arr[0] > arr[2]:
                res += f(arr, 2,0, 1, n,res)
            else:
                res += f(arr,0,2,1,n,res)
    print("Yes")
    for s in res:
        print(s)
main()
A,B,K=map(int,input(),split())
if A>=K:
  print(A-K,B)
elif K>A and A+B>=K:
  print(0,B-K+A)
else:
  print(0,0)

### FIXED CODE ###

A,B,K=map(int,input().split())
if A>=K:
  print(A-K,B)
elif K>A and A+B>=K:
  print(0,B-K+A)
else:
  print(0,0)
a,b=input().split()
if a==b:
    print(3)
elif a[0]=b[0] and a[1]=b[1] and a[2]!=b[2]:
    print(2)
elif a[0]=b[0] and a[1]!=b[1] and a[2]=b[2]:
    print(2)
elif a[0]!=b[0] and a[1]=b[1] and a[2]=b[2]:
    print(2)
elif a[0]!=b[0] and a[1]!=b[1] and a[2]!=b[2]:
    print(0)
else :
    print(1)  

### FIXED CODE ###

S=input()
T=input()
ans=0
for i in range(3):
 if S[i]==T[i]:
     ans+=1
print(ans)
from numba import njit
@njit("i8(i8)")

def solve(s,k):
  l=[i for i in s]
  ans=l
  mae=[]
  for i in range(len(s)-1):
    nlen=i+1
    for j in range(len(l)-1):
      lj=l[j+1]
      now=l[j]+lj[nlen-1:]
      mae.append(now)

    ans.extend(mae)
    l=mae
    mae=[]

  ans=list(set(ans))
  ans.sort()
  print(ans[k-1])


s=input()
k=int(input())
solve(s,k)

### FIXED CODE ###

s=input()
k=int(input())
ans=[]

for i in range(len(s)):
  for j in range(i+1,min(k+i+1,len(s)+1)):
    ans.append(s[i:j])

ans=list(set(ans))
ans.sort()
print(ans[k-1])
n=int(input())
s=list(input().strip().split() for _ in range(n))
x=input().strip()

ans=0
isis=False
for ss,tt in s:
  if isis:
    ans += (tt)
  if ss==x:
    isis=True
print(ans)

### FIXED CODE ###

n=int(input())
s=list(input().strip().split() for _ in range(n))
x=input().strip()

ans=0
isis=False
for ss,tt in s:
  if isis:
    ans += int(tt)
  if ss==x:
    isis=True
print(ans)
# coding: utf-8
import itertools
import sys

N, K = map(int, input().split())
# lst = [int(input()) for _ in range(N)]
lst = [int(i) for i in sys.stdin]
# lst2 = list(itertools.combinations(lst, K))
# print(lst2)

lst3 = []
# for l in lst2:
for l in itertools.combinations(lst, K):
    print(l)
    diff = max(l)-min(l)
    lst3.append(diff)

print(min(lst3))

### FIXED CODE ###

# coding: utf-8
import itertools

N, K = map(int, input().split())
lst = sorted([int(input()) for _ in range(N)], reverse=True)

ans = 10000000000
for i in range(N-K+1):
    l = lst[i]-lst[i+K-1]
    if l < ans:
        ans = l
print(ans)
import itertools

N=int(input())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))


Ns=list(itertools.permutations(range(1,N+1)))
PO=Ns.index(P)
QO=Ns.index(Q)
print(abs(Po-QO))


### FIXED CODE ###

import itertools

N=int(input())
p=list(map(str,input().split()))
q=list(map(str,input().split()))
P=''.join(p)
Q=''.join(q)

ns=list(itertools.permutations(range(1,N+1)))
Ns=[]
for i in range(len(ns)):
    temparr=[]
    for j in range(N):
        a=ns[i][j]
        temparr.append(str(a))
    b=''.join(temparr)
    Ns.append(b)

PO=Ns.index(P)
QO=Ns.index(Q)
print(abs(PO-QO))
s=list(input())
if s.sorted==["a","b","c"]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

s=input()
if s.count("a")==1 and s.count("b")==1 and s.count("c")==1:
    print("Yes")
else:
    print("No")
from collections import deque
S = deque(list(input().strip()))
Q = int(input())
cnt = 0
for i in range(Q):
    q = list(input().split())
    if len(q)==1:
        cnt += 1
    else:
        F = int(q[1])
        C = q[2]
        if cnt%2==0:
            if F==1:
                S.appendleft(C)
            else:
                S.append(C)
        else:
            if F==1:
                S.append(C)
            else:
                S.appendleft(C)
if cnt%2==0:
    print("".join(S))
else:
    S = S[::-1]
    print("".join(S))

### FIXED CODE ###

from collections import deque
S = deque(list(input().strip()))
Q = int(input())
cnt = 0
for _ in range(Q):
    q = list(input().split())
    if int(q[0])==1:
        cnt += 1
    else:
        if cnt%2==0:
            if int(q[1])==1:
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if int(q[1])==1:
                S.append(q[2])
            else:
                S.appendleft(q[2])
if cnt%2==0:
    print("".join(S))
else:
    S.reverse()
    print("".join(S))
N, Q = [int(item) for item in input().split()]

tree_list = [input() for _ in range(1,N)]
tree_list_int = [list(map(int,i.split())) for i in tree_list]
action_list = [input() for _ in range(Q)]
action_list_int = [list(map(int, i.split())) for i in action_list]

class Node:
    def __init__(self, data):
        self.data = data
        self.cnt = 0
        self.child = []


class tree:
    def __init__(self, N, tree_list_int):
        self.node_list = [Node(i) for i in range(1,N+1)]

        for i, j in tree_list_int:
            self.node_list[i-1].child.append(self.node_list[j-1])


    def adder(self, node, val):
        node.cnt += val

        if not node.child:
            return node.cnt

        for next_child in node.child:
            self.adder(next_child, val)

                

        
ins=tree(N, tree_list_int)

for pos, val in action_list_int:
    ins.adder(ins.node_list[pos-1], val)

res = str(ins.node_list[0].cnt)
for i in range(1, N):
    res += ' ' + str(ins.node_list[i].cnt)

print(res)


### FIXED CODE ###

N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0 for _ in range(N)]

linked_node_list = [[] for _ in range(N)]

for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b)
    linked_node_list[b].append(a)


for index, val in query_list_int:
    val_list[index-1] += val

stack = [0]
parent = [0] * (N+1)

while True:
    v=stack.pop()
    for child in linked_node_list[v]:
        if child != parent[v]:
            parent[child] = v
            stack.append(child)
            val_list[child] += val_list[v]
    if not stack:
        break

print(*val_list)
import sys
import itertools
import copy
ORG=map(int, sys.stdin.readline().split())
K=int(sys.stdin.readline().strip())
L=list( itertools.product(range(3), repeat=K) )

for x in L:
    ABC=copy.deepcopy(ORG)
    ABC[x[0]]*=2
    ABC[x[1]]*=2
    ABC[x[2]]*=2
    if ABC[0]<ABC[1]<ABC[2]:
        print "Yes"
        quit()
else:
    print "No"


### FIXED CODE ###

import sys
import itertools
import copy
ORG=map(int, sys.stdin.readline().split())
K=int(sys.stdin.readline().strip())
L=list( itertools.product(range(3), repeat=K) )

for l in L:
    ABC=copy.deepcopy(ORG)
    for x in l:
        ABC[x]*=2
    if ABC[0]<ABC[1]<ABC[2]:
        print "Yes"
        quit()
else:
    print "No"
a, b, c, d = map(int, input().split())


one = [i for i in range(a, b)]
two = [i for i in range(c, d)]

count = 0
for i in one:
    if i in two:
        count += 1
print(count)

### FIXED CODE ###

n = input()

a = [i for i in n]
b = [i for i in reversed(n)]

if a == b:
    print('Yes')
else:
    print('No')
import math
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
g = math.gcd(W, A[0][0]) 
for a in range(1, N):
	g = math.gcd(g, A[a][0])
W = W//g 
# print(g)
dp = [[0 for w in range(W+1)] for n in range(N+1)]
for i in range(W+1):
	dp[0][i] = 0
for p in range(1, N+1):
	for q in range(W+1):
		dp[p][q] = dp[p-1][q]
		if ((A[p-1][0]//g) <= q):
			dp[p][q] = max(dp[p][q], dp[p-1][q - (A[p-1][0]//g)] + A[p-1][1])
# print(dp)
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
inf = 10**10
V = 0
for a in range(N):
	V += A[a][1]
dp = [inf for v in range(V+1)]
dp[0] = 0
for p in range(N):
	for q in range(V - A[p][1], -1, -1):
		dp[q + A[p][1]] = min(dp[q + A[p][1]], dp[q] + A[p][0])
# print(dp)
ans = 0
for b in range(V+1):
	if (dp[b] <= W):
		ans = b
print(ans)
N = int(input())

T = [[] for i in range(N)]
F = [None for i in range(N-1)]
for i,n in enumerate(range(N-1)):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    F[i] = b-1

# print(T)

R = [None for i in range(N)]
def dfs(cur, mx, color):
    R[cur] = color
    if color == -1:
        mx = max(len(T[cur]), mx)
    else:
        mx = max(len(T[cur])+1, mx)
    d = 0
    mmx = mx
    for i,t in enumerate(T[cur], start=1):
        if i==color:
            d=1
        mmx = max(mmx, dfs(t, mx, i+d))
        # dfs(t, mx, i)
    return mmx
for bgn in range(N):
    if len(T[bgn])>0:
        break
# print(bgn)
M = dfs(bgn, 1, -1)
# print(R)
# print(F)
print(M)
for i,f in enumerate(F):
    print(R[f])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N = int(input())

E = []
T = [[] for i in range(N)]
for i,n in enumerate(range(N-1)):
    a,b = map(int,input().split())
    E.append((a-1,b-1))
    T[a-1].append(b-1)

# print(E)
# print(T)



R = [None for i in range(N)]
def dfs(using, cur):
    R[cur] = using
    i=0
    for t in T[cur]:
        if i==using:
            i+=1
        dfs(i,t)
        i+=1


dfs(-1, 0)

print(max(R)+1)
# print(K)
for e in E:
    print(R[e[1]]+1)

# print(K)
N = input()

if N/2 %2 != 0:
    print(0)

else:
    ls = list(map(int, input().split()))

    ls_sorted = sorted(ls)

    K = ls_sorted[N/2] - ls_sorted[N/2 - 1]

    print(K)

### FIXED CODE ###

N = int(input())


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

ls.sort()

K = ls[N//2] - ls[N//2 - 1]

print(int(K))
if set(input().split())==set([1,9,7,4]):
      print("Yes")
    else:
      print("No")  

### FIXED CODE ###

if set(input().split())==set("1974"):
	print("YES")
else:
	print("NO")
import math
Alp = [chr(ord('a') + i) for i in range(26)]
N = int(input())
k = int(math.ceil(math.log((25*N/26)+1,26)))
n = int(N-(26*(26**(k-1)-1)/25))
for i in range(k):
  if i<k-1:
    kre = int(n//(26**(k-1-i)))
    print(Alp[kre], end='')
    n -= int((26**(k-1-i))*kre)
  else:
    print(Alp[n-1], end='')

### FIXED CODE ###

import math
Alp = [chr(ord('a') + i) for i in range(26)]
N = int(input())
k = int(math.ceil(math.log((25*N/26)+1,26)))
n = int(N-(26*(26**(k-1)-1)/25))
for i in range(k):
  if i<k-1:
    if n%(26**(k-1-i))!=0:
      kre = int(n//(26**(k-1-i)))
    else:
      kre = int(n/(26**(k-1-i))-1)
    print(Alp[kre], end='')
    n -= int((26**(k-1-i))*kre)
  else:
    print(Alp[n-1], end='')