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

from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], True)]
    while len(q):
        cur, prev, lis, override = q.pop()
        idx = bisect_left(lis, A[cur])
        if override:
            if idx == len(lis):
                lis.append(A[cur])
            else:
                lis[idx] = A[cur]
            nxt_lis = lis
        else:
            nxt_lis = lis[:idx] + [A[cur]] + lis[idx+1:]
        ans[cur] = len(nxt_lis)
        nxt_override = (cur != 0)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, nxt_lis, nxt_override))
            nxt_override = False
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print(ans[i])


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

N,W=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  w,v=map(int,input().split())
  for j in range(1,W+1):
    if w<=j:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
    else:
      dp[i][j]=dp[i-1][j]
print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  w,v=map(int,input().split())
  for j in range(1,W+1):
    if w<=j:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
    else:
      dp[i][j]=dp[i-1][j]
print(dp[N][W])
### BUGGY CODE ###

class Segtree(object):
    import math
    def __init__(self, init_val, N, func_type):
        self.func = self.segfunc_min
        self.ide_ele = 10**9 # min
        if func_type == 'max':
            self.func = self.segfunc_max
            self.ide_ele = -10**9 # max
        elif func_type == 'gcd':
            self.func = self.segfunc_gcd
            self.ide_ele = 0 # gcd
        elif func_type == 'lcm':
            self.func = self.segfunc_lcm
            self.ide_ele = 1 # lcm
        elif func_type == 'add':
            self.func = self.segfunc_add
            self.ide_ele = 0 # add

        self.num = 2**(N-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        self.init_val = init_val

        n = len(self.init_val)
        self.seg[self.num-1:n+self.num-1] = self.init_val[:n]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.func(res,self.seg[p])
            if q&1 == 1:
                res = self.func(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res,self.seg[p])
        else:
            res = self.func(self.func(res,self.seg[p]),self.seg[q])
        return res

    def segfunc_min(self, a, b):
        if a > b:
            return b
        return a

    def segfunc_max(self, a, b):
        if a >= b:
            return a
        return b

    def segfunc_gcd(self, a, b):
        return math.gcd(a,b)

    def segfunc_lcm(self, a, b):
        return a*b//math.gcd(a,b)

    def segfunc_add(self, a, b):
        return a+b
N,x = map(int,input().split())
a = list(map(int,input().split()))
res = 10**18
seg = Segtree(a+a, 2*N, 'min')
# print(seg.seg)
for k in range(N-1,-1,-1):
    tmp = k*x
    tmp += sum([seg.query(N+i-k,N+i+1) for i in range(N)])
    res = min(res,tmp)
print(res)

### FIXED CODE ###

N,x = map(int,input().split())
a = list(map(int,input().split()))
res = 10**18
d = [[0]*N for _ in range(N)]
for i in range(N):
    d[i][0] = a[i]
    for k in range(1,N):
        d[i][k] = min(d[i][k-1], a[i-k])

for k in range(N-1,-1,-1):
    tmp = k*x
    tmp += sum([d[i][k] for i in range(N)])
    res = min(res,tmp)
print(res)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count("AC")) 

### FIXED CODE ###

n, q = map(int, input().split())
S = input()
flag = False
L = [0 for _ in range(n)]
cnt = 0
for i, s in enumerate(S):
    if flag:
        if s == "C":
            cnt += 1
        flag = False
    if s == "A":
        flag = True
    L[i] = cnt

for _ in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    print(L[r] - L[l])
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
t=[[] for j in range(64)]
l=[0 for _ in range(n)]
ll=l[:]
for i in range(64):
    for j in range(n):
        if i == 0:
            l[j]=a[j]
        else:
            l[j]=ll[ll[j]-1]
    ll=l[:]
    t[i]=l[:]
ans=1

for i in range(64):
    r = k%2
    k = k//2
    if r == 1:
        ans = t[i][ans-1]
    if k == 0:
        print(ans)
        exit()

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
dic = {1:1}
his=[1]
p=1
s=0
g=0
step=1
for i in range(k):
    t=a[p-1]
    if (t in dic and dic[t]==1):
        s=t
        g=a[t-1]
        break
    else:
        dic[t]=1
    step+=1
    his.append(t)
    p=t
x=his.index(t)
o=step-x
lp=his[x:]
k-=x
#print(x,o,his,lp)
#print(dic)
print(lp[k%o])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=1
for i in range(n):
  l=a.pop()
  if l == 0:
    s=0
    break
  else:
    s=s*l

if s>10**18:
  print(-1)
else:
  print(s)

### FIXED CODE ###

from collections import deque
n=int(input())
a=deque()
a=list(map(int,input().split()))
s=0
if a.count(0) == 0:
  s=1
  for i in range(n):
    l=a.pop()
    s=s*l      
  
    if len(str(s)) >= 19:
      if s == 10**18 and i==n-1:
        break
      s=-1
      break

    
print(s)
### BUGGY CODE ###

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

if len(a) == len(set(a)):
    for i in range(n):
        print(0)
else:
    set = set(a)
    count = [a.count(x) for x in set]
    ans = sum([x * (x - 1) // 2 for x in count])

    for i in range(n):
        print(ans - a.count(a[i]) + 1)


### FIXED CODE ###

from collections import Counter

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

if len(a) == len(set(a)):
    for i in range(n):
        print(0)
else:
    kw = Counter(a)
    ans = sum([x * (x - 1) // 2 for x in kw.values()])

    for i in range(n):
        print(ans - kw[a[i]] + 1)
### BUGGY CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
dp = [0]*(1+W)
w,v = WV[0]
dp[w:] = [v]*(W+1-w)
for i in range(1,N):
    dp_t = dp.copy()
    w,v = WV[i]
    for j in range(W+1):
        if j+w>W:
            break
        tmp = dp[j] + v
        dp_t[j+w] = max(dp[j+w], tmp)
    dp = dp_t.copy()
print(max(dp))

### FIXED CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
dp = [0]*(1+W)
w,v = WV[0]
dp[w:] = [v]*(W+1-w)
for i in range(1,N):
    w,v = WV[i]
    for j in range(W, w-1, -1):
        tmp = dp[j-w] + v
        dp[j] = max(dp[j], tmp)
print(max(dp))
### BUGGY CODE ###

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.bit = [0]*n
        self.n = n
    def add(self, ind, num):
        while(ind <= self.n):
            self.bit[ind - 1] += num
            ind += ind & -ind
    def sum(self, ind):
        ret = 0
        while(ind > 0):
            ret += self.bit[ind-1]
            ind -= ind & -ind
        return ret

class Binary_Indexed_Tree_RAQ_RSQ():
    def __init__(self,n):
        self.p = Binary_Indexed_Tree(n+1)
        self.q = Binary_Indexed_Tree(n+1)

    def add(self, s,t,x):
        t += 1
        self.p.add(s,-x*s)
        self.p.add(t, x*t)
        self.q.add(s,x)
        self.q.add(t,-x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t)*t - self.p.sum(s) - self.q.sum(s)*s

n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
a = []
for i, c in enumerate(s):
    if c == "D":
        a.append(i)

BIT = Binary_Indexed_Tree_RAQ_RSQ(len(a))

ans = [0]*q

from bisect import bisect_left
for i, c in enumerate(s):
    if c == "M":
        j = bisect_left(a, i) - 1
        BIT.add(1, j+1, 1)
    elif c == "C":
        right = bisect_left(a, i) - 1
        for j, ki in enumerate(k):
            left = bisect_left(a, i-(ki-1))
            tmp = 0
            if left <= right:
                tmp = BIT.sum(left+1, right+1)
            ans[j] += tmp
print(*ans, sep="\n")

### FIXED CODE ###

# コピペ https://atcoder.jp/contests/dwacon5th-prelims/submissions/7670569
# 自分の https://atcoder.jp/contests/dwacon5th-prelims/submissions/7822126
# とほぼ変わらないのに自分のものはTLEするので検証
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    print(a.index(i)+1,end='')
    if i!=n+1:
        print(" ",end="")
print()

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[a[i]-1]=i+1

for i in range(n):
    print(b[i],end="")
    if i!=n-1:
        print(" ",end="")
print()
### BUGGY CODE ###

s = str(input())
cnt=0
while '10' in s or '01' in s:
    cnt+=s.count('10')
    s=s.replace('10', '') 
    cnt+=s.count('01')
    s=s.replace('01', '') 
print(cnt*2)

### FIXED CODE ###

#120 C
S =input()
print(min(S.count('0'),S.count('1'))*2)
### BUGGY CODE ###

while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [raw_input() for i in range(H)]
	S = [[0]*W for i in range(H)]
	L = ans = 0
	for h in range(H):
		for w in range(W):
			if A[h][w] == ".":
				L += 1
			else:
				L = 0
			S[h][w] = L
			if L > 0:
				a = L
				for hi in range(h-1,-1,-1):
					if S[hi][w] == 0:
						break
					a = min(a,S[hi][w])
					ans = max(ans,a*(h-hi+1))
	print ans

### FIXED CODE ###

while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 0
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = L
				for hi in range(B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans
### BUGGY CODE ###

n=int(input())
def lucas(n):
	if n==0:
		return 2
	if n==1:
		return 1
	if n>1:
		return lucas(n-1)+lucas(n-2)
print(lucas(n))


### FIXED CODE ###

n=int(input())
def lucas(n):
	a, b = 2, 1
	for i in range(n):
		a, b = b, a+b
	return a
print(lucas(n))
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            CNT += gcd(i,j,k)
print(CNT)

### FIXED CODE ###

import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        GCD = gcd(i,j)
        if GCD == 1:
            CNT += K
        else:
            for k in range(1, K+1):
                if gcd(GCD,k) != 1:
                    CNT += gcd(GCD,k)
                else:
                    CNT += 1
print(CNT)
### BUGGY CODE ###

import copy
import collections

#Input
n = int(input())
l_a = list(map(int, input().split()))

#Process
for i in range(n):
    l_o = copy.copy(l_a)
    del l_o[i]
    l_c = list(collections.Counter(l_o).values())
    Ans = 0
    for i in range(len(l_c)):
        for j in range(l_c[i] - 1):
            Ans += (j + 1)
    print(Ans)

### FIXED CODE ###

import collections

#Input
n = int(input())
l_a = list(map(int, input().split()))

#Process
d_c = collections.Counter(l_a)
l_c = list(d_c.values())

#N個から選ぶ方法
o = 0
for i in range(len(l_c)):
    if(l_c[i] != 1):
        o += int((l_c[i] - 1) * l_c[i] / 2)

#Output
for i in range(n):
    print(o - d_c[l_a[i]] + 1)
### BUGGY CODE ###

import collections

n = int(input())
s = []

s_append = s.append
for _ in range(n):
    s_append(input())

pop_times = collections.Counter(s)
most_common_word = []

most_common_word_append = most_common_word.append
for i in pop_times.most_common():
    if pop_times.most_common()[0][1] == i[1]:
        most_common_word_append(i[0])

for x in sorted(most_common_word):
    print(x)


### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
d = {}
ans = []

for st in s:
    d[st] = d.get(st, 0) + 1

t = max(d.values())
ans_append = ans.append

for x in d:
    if d[x] == t:
        ans_append(x)

ans = sorted(ans)
for x in ans:
    print(x)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
suml = sum(l)
xs = set()
for i in range(2**n):
    x = []
    for j in range(n):
        if ((i >> j) & 1):
            x.append(l[j])
    xs.add(sum(x))
xs.remove(0)
ans = float('Inf')
for i in xs:
    j = abs(2*i - suml)
    ans = min(ans,j)
print(ans)

### FIXED CODE ###

from itertools import accumulate
n = int(input())
l = list(map(int,input().split()))
suml = sum(l)
accl = list(accumulate([0]+l))
ans = float('Inf')
for i in range(1,n):
    x = accl[i]
    j = abs(2*x - suml)
    ans = min(ans,j)
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ac_list = [0]*n

for i in range(n-1):
  if s[i:i+2]=='AC':
    ac_list[i] += 1

for _ in range(q):
  l, r = map(int, input().split())
  print(sum(ac_list[l-1:r-1]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

N,K = map(int,input().split())
L = list(map(int,input().split()))
L.sort()
L.reverse()
count = K
ans = 0
for i in range(len(L)):
  if count != 0:
    L[i] = 0
    ans += 1
    count -= 1
    if sum(L) == 0:
      count = 0
      break
  else:
    break
print(count+sum(L))

### FIXED CODE ###

N,K = map(int,input().split())
L = list(map(int,input().split()))
L.sort()
count = K
ans = 0
if len(L)>K:
  for i in range(len(L)-K):
    ans += L[i]
  print(ans)
else:
  print(0)
### BUGGY CODE ###

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

ans = 0
for i in range(0,n-1):
    for j in range(i,n):
        ans += a[i] ^ a[j] 

mod = 10**9+7
ans %= mod
print(ans)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
c=0
for i in range(61):
  i=2**i
  t=sum(i&b and 1 for b in a)
  c=(c+t*(n-t)*i)%(10**9+7)
print(c)
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr_1 = [list(map(int, input().split())) for _ in range(q)]
lr = lr_1.copy()
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = {}
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans[str(l) + "-" + str(r)] = (bit.sum(r) - bit.sum(l - 1))
        pos += 1
        if pos == q:
            break
    if pos == q:
        break

for l, r in lr_1:
    print(ans[str(l) + "-" + str(r)])


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append([l, r, i])
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = [-1 for _ in range(q)]
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans[lr[pos][2]] = bit.sum(r) - bit.sum(l - 1)
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
    
print(*ans, sep="\n")
### BUGGY CODE ###

n,m = map(int, input().split())
x = sorted(list(map(int, input().split())))
l = [0] * (m-1)
ans = 0
if n < m:
  for i in range(m-1):
    l[i] = x[i+1] - x[i]
  for _ in range(m-n):
    ans += min(l)
    l.pop(l.index(min(l)))
print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
x = sorted(list(map(int, input().split())))
l = [0] * (m-1)
if n >= m:
  print(0)
  exit()
else:
  for i in range(m-1):
    l[i] = x[i+1] - x[i]
  print(sum(sorted(l)[:m-n]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    yen = [6 ** i for i in range(1, 7)]
    yen += [9 ** i for i in range(1, 6)]
    yen = [i for i in yen if i <= N]
    yen.sort(reverse=True)

    def MIN(a, b):
        if a > b:
            return b
        else:
            return a

    @lru_cache(maxsize=None)
    def dfs(x, n, m):
        n += 1
        for y in yen:
            if n >= m:
                return n
            if y > x:
                continue
            if x - y < 6:
                return n + x - y
            m = MIN(dfs(x - y, n, m), m)
        return m

    print(dfs(N, 0, N))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    yen = [6 ** i for i in range(1, 7)]
    yen += [9 ** i for i in range(1, 6)]
    yen = [i for i in yen if i <= N]
    yen.sort(reverse=True)

    def MIN(a, b):
        if a > b:
            return b
        else:
            return a

    @lru_cache(maxsize=None)
    def dfs(x, n, m):
        n += 1
        for y in yen:
            if n >= m:
                return n
            if y > x:
                continue
            if x - y < 6:
                return n + x - y
            m = MIN(dfs(x - y, n, m), m)
        return m

    print(dfs(N, 0, N))

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

# -*- coding: utf-8 -*-
v_max = 100010
INF = 1000000100
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    weight[i], value[i] = map(int, input().split())

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max+1):
    # print("v_sum: " + str(j) + " , weight: " + str(dp[n][j]))
    if dp[n][j] <= w:
        result = j
print(result)


### FIXED CODE ###

# -*- coding: utf-8 -*-
v_max = 100010
INF = 1000000100
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    weight[i], value[i] = map(int, input().split())

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max+1):
    if dp[n][j] <= w:
        result = j
print(result)
### BUGGY CODE ###

import math

def f(A,B,x):
    return math.floor(A*x/B) - A*math.floor(x/B)

A,B,N = map(int,input().split())
ans = 0
if B <= N:
    N = B
for x in range(B//A , N+1):
    n = f(A,B,x)
    if n > ans:
        ans = n

print(ans)
        

### FIXED CODE ###

import math
def f(A,B,x):
    return math.floor(A*x/B) - A*math.floor(x/B)

A,B,N = map(int,input().split())
x = min(N,B-1)
print(f(A,B,x))
### BUGGY CODE ###

import collections, sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for d in D:
    events += [[d, 2]]
events.sort()
block = set()
ans = []
for e in events:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            ans += [min(block)]
        else:
            ans += [-1]
print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
    events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
m = float('inf')
for e in events:
    if e[1] == 0:
        block.remove(e[2])
        if m == e[2]:
            if block:
                m = min(block)
            else:
                m = float('inf')
    elif e[1] == 1:
        block.add(e[2])
        m = min(m, e[2])
    else:
        if block:
            if m == float('inf'):
                ans[e[2]] = -1
            else:
                ans[e[2]] = m
print(*ans, sep='\n')
### BUGGY CODE ###

n,x,y=map(int,input().split())
l=[]
for i in range(n-1):
  for k in range (i+1,n):
    if k<x-1 or i>y-1:
      l.append(k-i)
    else:
      l.append(min(abs(x-1-i)+abs(y-1-k)+1,k-i))
for i in range(1,n):
  print(l.count(i))

### FIXED CODE ###

from collections import Counter
n,x,y=map(int,input().split())
l=[]
for i in range(n-1):
  for k in range (i+1,n):
      l.append(min(abs(x-1-i)+abs(y-1-k)+1,k-i))
S=Counter(l)
for i in range(1,n):
  print(S[i])
### BUGGY CODE ###

K=int(input())
import numpy
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum+=numpy.gcd(numpy.gcd(i,j),k)
print(sum)

### FIXED CODE ###

K=int(input())
from math import gcd
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum+=gcd(gcd(i,j),k)
print(sum)