Harryxun/stf_run huggingface dataset:
import math
N, P = map(int, input().split())
if N == 1:
	print(P)
elif N > math.log2(P):
	print(1)
else:
	ans = 1
	x = int(P ** (1.0 / (N * 1.0)))
	for i in range(2, x + 1):
		if P % (i ** N) == 0:
			ans = i
	print(ans)

### FIXED CODE ###

import math	
N, P = map(int, input().split())
if N == 1:
	print(P)
else:
	ans = 1
	for i in range(2, P):
		if N * math.log(i) > math.log(P):
			break
		if P % (i ** N) == 0:
			ans = i
	print(ans)
a=str(input())
b=str(input())
print(a+b)

### FIXED CODE ###

a,b=input().split()
print(b+a)
import sys
N, M = map(int, sys.stdin.readline().split())
A = sorted(list(map(int, sys.stdin.readline().split())))
BC = [list(map(int,sys.stdin.readline().split())) for i in range(M)]
for i in range(len(BC)):
	BC[i] = BC[i][::-1]
BC = sorted(BC, reverse=True)
c = 0
for j in BC:
    for k in range(c, c + j[1]):
        if A[k] < j[0]:
            A[k] = j[0]
    c = c + j[1]
print(sum(A))

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
CB = deque([])
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
CB = sorted(CB, reverse=True)
flag = False
c = 0
I = 0
for i in CB:
    I += i[1]
    if flag:
        break
    while c < I:
        if c >= N:
            break
        if A[c] < i[0]:
            A[c] = i[0]
            c += 1
        else:
            c = I
            flag = True
print(sum(A))
from collections import Counter

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

AC = Counter(A)
BC = Counter(B)
if N < max((AC + BC).values()):
    print('No')
    exit()

a = 0
b = 0
while a < N:
    if A[a] == B[a]:
        while A[a] == B[b] or A[b] == B[a]:
            b = (b + 1)
            if b >= N:
                raise Exception
        B[a], B[b] = B[b], B[a]
    a += 1

print('Yes')
print(*B)


### FIXED CODE ###

from collections import Counter
from heapq import heappush, heappop


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

AC = Counter(A)
BC = Counter(B)
S = AC + BC

q = []
for k, v in S.items():
    heappush(q, (-v, k))

ans = []
while q:
    v, k = heappop(q)
    v = -v
    if v != S[k]:
        if S[k] != 0:
            heappush(q, (-S[k], k))
    else:
        if v != 1:
            heappush(q, (-(v - 1), k))
        if v > N:
            print('No')
            exit()
        else:
            if AC[k] > 0:
                a = k
                for l in BC.keys():
                    if l != k:
                        b = l
                        break
            else:
                b = k
                for l in AC.keys():
                    if l != k:
                        a = l
                        break
            ans.append((a, b))
            S[a] -= 1
            S[b] -= 1
            AC[a] -= 1
            if not AC[a]:
                AC.pop(a)
            BC[b] -= 1
            if not BC[b]:
                BC.pop(b)

print('Yes')
ans.sort()
X = [b for a, b in ans]
print(*X)
s = str(input()) 

k_lower = s[:k-1]+s[k-1].lower()+s[k:]
print(k_lower)


### FIXED CODE ###

n,k = map(int, input().split())
s = str(input()) 

print(s[:k-1]+s[k-1].lower()+s[k:])
import sys
input = sys.stdin.readline
N, K = [int(x) for x in input().split()]
h = []
for _ in range(N):
    h.append(int(input()))
h.sort()
a = N - K
i = 0
h_left = h[:a]
h_right = h[K:]
h_middle = h[a:K]
ans = min(h_middle[-1] - h_left[0], h_right[-1] - h_middle[0]) 
for i in range(len(h_right)-1):
    j = a - i - 1
    ans_ = h_right[i] - h_left[j]
    ans = min(ans, ans_)
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
n,m=map(int,input().split())
sc=sorted([list(map(int,input().split())) for i in range(m)])
ans=[0 for i in range(n)]
res=True
ans[sc[0][0]-1]=sc[0][1]
for i in range(1,m):
    if sc[i][0]==sc[i-1][0] and sc[i][1]!=sc[i-1][1]:
        res=False
        break
    else:
        ans[sc[i][0]-1]=sc[i][1]

ans2=int("".join([str(i) for i in ans])) if res and not (n>1 and ans[0]==0) else -1
print(ans2)


### FIXED CODE ###

n,m=map(int,input().split())
sc=sorted([list(map(int,input().split())) for i in range(m)])
ans=[0 for i in range(n)]
res=True
for i in range(m):
    if (i>0 and sc[i][0]==sc[i-1][0] and sc[i][1]!=sc[i-1][1]) or (n>1 and sc[i][0]==1 and sc[i][1]==0):
        res=False
        break
    else:
        ans[sc[i][0]-1]=sc[i][1]

if n>1 and ans[0]==0:
    ans[0]=1

ans2=int("".join([str(i) for i in ans])) if res else -1
print(ans2)
N, K = map(int, input().split(" "))
routs = {}
location = [0 for i in range(N + 1)]
tereporter = list(map(int, input().split()))
for i in range(N):
  routs[i] = tereporter[i] - 1
present_location = 0
n = 0
for i in range(K):
  n += 1
  present_location = routs[present_location]
  if location[present_location] == 0:
    location[present_location] = n
  else:
  loop = n - location[present_location]
  if (K - location[present_location]) % loop == 0:
    break
  else:
    for i in range((K - location[present_location]) % loop):
      present_location = routs[present_location]
	break
print(present_location + 1)



### FIXED CODE ###

N, K = map(int, input().split(" "))
routs = {}
location = [0 for i in range(N + 1)]
tereporter = list(map(int, input().split()))
for i in range(N):
  routs[i] = tereporter[i] - 1
present_location = 0
n = 0
for i in range(K):
  n += 1
  present_location = routs[present_location]
  if location[present_location] == 0:
    location[present_location] = n
  else:
    loop = n - location[present_location]
    if (K - location[present_location]) % loop == 0:
      break
    else:
      for i in range((K - location[present_location]) % loop):
        present_location = routs[present_location]
      break
print(present_location + 1)
def solve():
    a, b, c = map(int, input().split())
    print((a + b)*c/2)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print(int((a + b) * h / 2))
n = int(input())
a = [int(i) for i in input().split()]
min = (10**9,None)
for i in range(n-1):
    if a[i] < 0:
        a[i] *= (-1)
        a[i+1] *= (-1)
    if min[0] > abs(a[i]):
        min = (abs(a[i],i))
if a[-1] < 0:
    a[-1]**=(-1)
    a[min[1]]**=(-1)
print(sum(a))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
m,ans = 10**9,0
for i in range(n-1):
    m = min(m,abs(a[i]))
    if a[i] < 0:
        a[i]*=(-1)
        a[i+1]*=(-1)
if a[-1] >= 0:
    print(sum(a))
else:
    a[-1] *= (-1)
    m = min(m,abs(a[i+1]))
    print(sum(a)-m*2)
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    a = i_input()
    b = i_input()

    if a == b:
        print('EQUAL')
    else:
        a > b:
        print('GREATER')
    else:
        print('LESS')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    a = i_input()
    b = i_input()

    if a == b:
        print('EQUAL')
    elif a > b:
        print('GREATER')
    else:
        print('LESS')

if __name__ == '__main__':
    main()
n = int(input())
s = list(map(int, input().split(" ")))
# n = 2
# s = list(reversed(range(1, 2 ** n + 1)))

s = sorted(s, reverse=True)
from collections import deque

def solve():
    parents = [s[0]]
    k = 1

    while k < len(s):
        newparents = list(parents)
        for p in parents:
            print("Check", p)
            if p > s[k]:
                print("Take", s[k])
                newparents.append(s[k])
                k += 1
            else:
                print("No")
                exit(1)
        parents = sorted(newparents, reverse=True)
    print("Yes")
solve()


### FIXED CODE ###

import bisect

n = int(input())
s = list(map(int, input().split(" ")))
# n = 18
# s = list(reversed(range(1, 2 ** n + 1)))

s = sorted(s)
from collections import deque

def solve():
    global s

    parents = [s[-1]]
    s.pop()

    for i in range(n):
        newparents = list(parents)
        k = len(s)
        dropped = set()
        # print(parents)
        for p in parents:
            oldK = k
            k = bisect.bisect(s, p - 1, 0, k) - 1
            # print("Old", oldK, k, s[k], p)
            if k == -1:
                print("No")
                exit(0)

            newparents.append(s[k])
            dropped.add(k)
        s = [x for i, x in enumerate(s) if i not in dropped]
        parents = sorted(newparents, reverse=True)

    # print(parents)
    # print(k)
    if k == len(s):
        print("Yes")
    else:
        print("No")
solve()
s = input()
print(1 if s.startswith("1"*int(input())) else s.replace("1","")[0])

### FIXED CODE ###

a = input()[:int(input())]
j = set(sorted(set(a), key=a.index)[:2])
j.discard("1")
print(list(j)[0] if j else 1)
N,Q = list(map(int,input().split()))
ab = [[int(i) for i in input().split()] for _ in range(N-1)]
px = [[int(i) for i in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)

value = [0]*(N+1)
for p,x in px:
  value[p] += x

def dfs(x,parent,add):
  value[x] += add
  for i in graph[x]:
    if i == parent:
      continue
    dfs(i,x,value[x])

dfs(1,0,0)
answer = ' '.join(map(str,value[1:]))
print(answer)

### FIXED CODE ###

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

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
s = list(input())

d = { x for x in s}

if len(d) == 1:
  print ("NO")
else :
  print ('YES')
  
  

### FIXED CODE ###

d = list(input())

s = {i for i in d}

if len(s) == 1:
  print ("No")
else :
  print ("Yes")
n = int(input())
lines = [[int(i) for i in input().split()] for i in range(n)]
e = map(int, lines().split()) 
output =(e(0)-e(2))*(e(1)-e(3))
print output

### FIXED CODE ###

H, W = map(int, input().split())
h, w = map(int, input().split())
output = (H-h)*(W-w)
print (output)
A = int(input())
B = int(input())
if A>12:
    print(B)
elif 13>A>5:
    print(round(B/2))
else:
    print(0)


### FIXED CODE ###

a,b = map(int,input().split());print(b//-~(a<13)*(a>5))
n = int(input())

def kaidan(n):
    if n <= 1:
        return 0
    else:
        return n - 1 + kaidan(n - 1)

print(kaidan(n))

### FIXED CODE ###

n = int(input())

print((n * (n - 1)) // 2)
N,M,Q=map(int,input().split())
S=[list(map(int,input().split())) for _ in range(Q)]

n=0
for i in range(N):
    n+=int(10**i)
m=0
for i in range(N):
    m+=int(M*10**i)
ans=[]
for j in range(n,m):
    J=str(j)
    total=[]
    for k in range(Q):
        if int(J[S[k][1]-1])-int(J[S[k][0]-1])==int(S[k][2]):
            total.append(int(S[k][3]))
    ans.append((sum(total)))
    
ans=sorted(ans,reverse=True)  
print(ans[0])

### FIXED CODE ###

import itertools
N,M,Q=map(int,input().split())
S=[list(map(int,input().split())) for _ in range(Q)]


ans=0
for A in itertools.combinations_with_replacement(range(1,M+1),N):
    A=sorted(A)
    total=0
    for k in range(Q):
        if A[(S[k][1]-1)]-A[S[k][0]-1]==S[k][2]:
            total+=S[k][3]
    if total>ans:
        ans=total

print(ans)
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)


### FIXED CODE ###

import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        if mod_m >= 1:
            s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1' and (mod_m == 0 or mod_m == -1):
        print(0)
    elif x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
N = int(input())
A = [int(i) for i in input().split()]
GCD = [gcd(*[e for s,e in enumerate(A) if s!=i]) for i in range(N)]
print(max(GCD))

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
gcda = [A[0]]
gcdb = [A[-1]]
for i in range(N-2):
    gcda.append(gcd(gcda[-1],A[i+1]))
    gcdb.append(gcd(gcdb[-1],A[-(i+2)]))
gcdb.reverse()
GC = [gcdb[0]]
for i in range(N-2):
    GC.append(gcd(gcda[i],gcdb[i+1]))
else:
    GC.append(gcda[-1])
print(max(GC))
a,b,c=input(int()).split()
s = b
aa = int(a)
cc = int(c)
bb = int(b)
for i in  range(10):
    d= aa * cc - bb
    cc = d
    print (int(d))

### FIXED CODE ###

a,b=input().split()
if int(a) >= 13 :
    print(int(b))
if int(a) >= 6 and int(a) <=12 :
    print(round(int(b) / 2))
if int(a) <= 5 :
    print(0)
S=input()
n=len(S)
ans=0

for i in range(n):
    for j in range(i,n):
        if S[i:j+1].count("A","C","G","T")==j-i+1:
            ans=max(ans,j-i+1)
print(ans)

### FIXED CODE ###

S=input()

ans=0
tmp=0
for i in range(len(S)):
    if S[i] in ("A","C","G","T"):
        tmp+=1
    else:
        ans=max(ans,tmp)
        tmp=0
ans=max(ans,tmp)
print(ans)
N=int(input())
S=input()

if

### FIXED CODE ###

n=int(input())
s=input()
count=0
for i in range(n-2):
  if s[i]=='A' and s[i+1]=='B' and s[i+2]=='C':
    count+=1
print(count)
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,T = map(int,input().split())
A = [int(i) for i in input().split()]

L_min = [mod for i in range(N)]
L_min[0] = A[0]
for i in range(1,N):
    L_min[i] = min(L_min[i-1],A[i])

A.reverse()
R_max = [0 for i in range(N)]
R_max[0] = A[0]
for i in range(1,N):
    R_max[i] = max(R_max[i-1],A[i])

R_max.reverse()

ans = 0
dif = 0
# print(R_max)
# print(L_min)
for i in range(1,N):
    if dif < R_max[i] - L_min[i]:
        dif = R_max[i] - L_min[i]
        r,l = R_max[i],L_min[i]
        # print(dif)
        ans = 1
    elif dif == R_max[i] - L_min[i]:
        if r == R_max[i]:
            pass
        else:
            r,l = R_max[i],L_min[i]
            ans += 1

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,T = map(int,input().split())
A = [int(i) for i in input().split()]

L_min = [mod for i in range(N)]
L_min[0] = A[0]
for i in range(1,N):
    L_min[i] = min(L_min[i-1],A[i])

A.reverse()
R_max = [0 for i in range(N)]
R_max[0] = A[0]
for i in range(1,N):
    R_max[i] = max(R_max[i-1],A[i])

R_max.reverse()

ans = 0
dif = -mod

for i in range(1,N):
    if dif < R_max[i] - L_min[i] and 0 < R_max[i] - L_min[i]:
        dif = R_max[i] - L_min[i]
        r,l = R_max[i],L_min[i]
        # print(dif)
        ans = 1
    elif dif == R_max[i] - L_min[i]:
        if r == R_max[i]:
            pass
        else:
            r,l = R_max[i],L_min[i]
            ans += 1

print(ans)
n=iinput())
s=list()
for i in range(n):
 s.append(input())
print(len(set(s)))

### FIXED CODE ###

n=int(input())
s=list()
for i in range(n):
 s.append(input())
print(len(set(s)))
l=[1]
p=[1]
N,X=map(int,input().split())
for i in range(N):
    l.append(l[i]*2+3)
    p.append(p[i]*2+1)
def calc(n,x):
    if n==0 and x==1:
        return 1
    if x==0 or x==1:
        return 0
    if x<=l[n]//2:
        return calc(n-1,x-1)
    elif x==l[n]//2+1:
        return p[n-1]+1
    else:
        return p[n-1]+1+calc(n-1,x-(l[n-1]+2))

print(calc(N,X))

### FIXED CODE ###

l = [1]
p = [1]
N, X = map(int, input().split())
for i in range(N):
    l.append(l[i] * 2 + 3)
    p.append(p[i] * 2 + 1)


def calc(n, x):
    if l[n] <= x:
        return p[n]
    if x == 0 or x == 1:
        return 0
    if x <= l[n] // 2:
        return calc(n - 1, x - 1)
    elif x == l[n] // 2 + 1:
        return p[n - 1] + 1
    else:
        return p[n - 1] + 1 + calc(n - 1, x - (l[n - 1] + 2))

print(calc(N, X))
N,K,S=map(int,input().split())
a=[]

for i in range(K):
  a.append(S)

if N>len(a):
  for i in range(N-len(S))
  a.append(S+1)
      
print(' '.join(map(str, a)))
  

### FIXED CODE ###

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

for i in range(K):
  a.append(S)

if N>len(a):
  for i in range(N-len(a)):
    if S==10**9:
      a.append(S-1)
    else:
      a.append(S+1)
      
print(' '.join(map(str, a)))
a,b=(int(i) for i in input().split())
peint(max(a+b,a-b,a*b))

### FIXED CODE ###

a,b=(int(i) for i in input().split())
print(max(a+b,a-b,a*b))
import sys
input=sys.stdin.buffer.readline

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**9)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**9,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

temp=[[0,0] for i in range(2**9)]

data=[[] for i in range(N+1)]
last=[-1 for i in range(N+1)]
for i in range(1,N+1):
    id=i
    while id>=2**9:
        data[i].append(vw[id])
        id//=2
    last[i]=id

def solve(v,L):
    n=len(data[v])
    for i in range(1,2**n):
        m=i.bit_length()
        temp[i][0]=temp[i-2**(m-1)][0]+data[m-1][0]
        temp[i][1]=temp[i-2**(m-1)][1]+data[m-1][1]
    ans=0
    for i in range(2**n):
        if L>=temp[i][1]:
            ans=max(ans,temp[i][0]+dp[last[v]][L-temp[i][1]])
    return ans

for i in range(int(input())):
    v,L=map(int,input().split())
    print(solve(v,L))


### FIXED CODE ###

import sys,random,time,bisect
input=sys.stdin.buffer.readline

start=time.time()
N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])
n, w = map(int, input().split())

dp = [[float('inf') for _ in range(10**5+1)] for i in range(n)]

v_sum = 0

for i in range(n):
    wi, vi = map(int, input().split())
    v_sum += vi
    if i == 0:
        dp[i][0] = 0
        dp[i][vi] = wi
    else:
        for k in range(v_sum+1):
            if k < vi:
                dp[i][k] = dp[i-1][k]
            else:
                dp[i][k] = min(dp[i-1][k], dp[i-1][k-vi]+wi)

for i in range(v_sum+1,-1,-1):
    if dp[n-1][i] <= w:
        print(i)
        exit()


### FIXED CODE ###

n, w = map(int, input().split())

dp = [[float('inf') for _ in range(10**5+1)] for i in range(n)]

for i in range(n):
    wi, vi = map(int, input().split())
    if i == 0:
        dp[i][0] = 0
        dp[i][vi] = wi
    else:
        for k in range(10**5+1):
            if k < vi:
                dp[i][k] = dp[i-1][k]
            else:
                dp[i][k] = min(dp[i-1][k], dp[i-1][k-vi]+wi)

for i in range(10**5+1)[::-1]:
    if dp[n-1][i] <= w:
        print(i)
        exit()