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

N, Ma, Mb = map(int,input().split())
a=[0]*N
b=[0]*N
c=[0]*N
for i in range(N):
    a[i], b[i], c[i] = map(int,input().split())

dp = [[[4001 for i in range(411)] for j in range(411)] for l in range(N+1)]

dp[0][0][0] = 0

for i in range(1,N+1):
    for j in range(400):
        for k in range(400):
            dp[i][j+a[i-1]][k+b[i-1]] = min(dp[i-1][j][k] + c[i-1],dp[i-1][j+a[i-1]][k+b[i-1]])
            dp[i][j][k] = min(dp[i - 1][j][k], dp[i][j][k])
s = min(400//Ma,400//Mb)

min = 4001
for i in range(1,s+1):
    x = dp[N][i*Ma][i*Mb]
    if x>0 and min > x:
        min = x

if min != 4001:
    print(min)
else:
    print(-1)


### FIXED CODE ###

N, Ma, Mb = map(int,input().split())
a=[0]*N
b=[0]*N
c=[0]*N
for i in range(N):
    a[i], b[i], c[i] = map(int,input().split())

dp = [[[4001 for i in range(411)] for j in range(411)] for l in range(N+1)]

dp[0][0][0] = 0

for i in range(1,N+1):
    for j in range(400):
        for k in range(400):
            if dp[i-1][j][k] == 4001:
                continue
            dp[i][j+a[i-1]][k+b[i-1]] = min(dp[i-1][j][k] + c[i-1],dp[i-1][j+a[i-1]][k+b[i-1]])
            dp[i][j][k] = min(dp[i - 1][j][k], dp[i][j][k])
s = min(400//Ma,400//Mb)

min = 4001
for i in range(1,s+1):
    x = dp[N][i*Ma][i*Mb]
    if x>0 and min > x:
        min = x

if min != 4001:
    print(min)
else:
    print(-1)
### BUGGY CODE ###

l, r = map(int, input().split())
mod1 = []
mod2 = []
for i in range(l,r+1):
  mod1.append(i%2019)

for i in range(len(mod1)-1):
  for j in range(i+1,len(mod1)):
    mod2.append((mod1[i]*mod1[j])%2019)

print(min(mod2))

### FIXED CODE ###

l, r = map(int, input().split())
mod1 = []
mod2 = []
cccc=0
for i in range(l,r+1):
  b=i%2019
  mod1.append(b)
  if b==0:
    cccc=1
    break
#print(mod1)
if cccc==1:
  print(0)
else:
  for i in range(len(mod1)-1):
    for j in range(i+1,len(mod1)):
      mod2.append((mod1[i]*mod1[j])%2019)
	#print(mod2)
  print(min(mod2))
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

for i in range(n):
    val = a.pop(i)
    sa = sorted(a)
    print(sa[-1])
    a.insert(i, val)

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

sa = sorted(a)
mx = sa[-1]
for val in a:
    if val != mx:
        print(sa[-1])
    else:
        print(sa[-2])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for _ in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    j = 0
    while j < W:
        block_count = 0
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                div_count +=1
                white_count = [0 for s in bin_str if s == "1"]
                white_count.append(0)
                break
        else:
            j+=1

        if div_count >= min_div_count:
            break

    else:
        min_div_count = div_count
print(min_div_count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for _ in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    
    for j in range(W):
        block_count = 0
        white_list = [0]*len(white_count)
        #print("j:"+str(j))
        is_over = False
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            
            white_list[block_count] += int(choco[k][j])
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                is_over = True

        if max(white_list)>K:
            break


        if is_over:
            div_count += 1
            white_count = white_list


        #print(white_list)   
        #print(white_count)
        #print("div_count"+str(div_count))
        if div_count >= min_div_count:
            break
    else:
        min_div_count = div_count
print(min_div_count)
### BUGGY CODE ###

#coding=UTF-8

def search(jun):
    global ans
    global R
    global Kost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += Kost[r[mae]][r[ba]]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono)-1) for mono in hyo]

Kost=[]
for idx in range(0,N,1):
    Kost.append([None]*N)

for idx in range(0,N,1):
    Kost[idx][idx]=0

miru=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])

    Kost[A][B]=C
    Kost[B][A]=C
    miru.append((A,B,C))
    miru.append((B,A,C))

while miru:
    nextmiru=[]
    for idx in range(0,N,1):
        for keiro in miru:
            tui=Kost[keiro[1]][idx]
            if tui==None:
                continue

            tmpKost=keiro[2]+tui
            if Kost[keiro[0]][idx]==None or tmpKost < Kost[keiro[0]][idx]:
                Kost[keiro[0]][idx]=tmpKost
                nextmiru.append((keiro[0],idx,tmpKost))
    miru=nextmiru

#for gyo in Kost:
#    print(gyo)

ans=None
search([])
print(ans)


### FIXED CODE ###

#coding=UTF-8

def search(jun):
    global ans
    global R
    global r
    global rCost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += rCost[mae][r[ba]]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono) -1 ) for mono in hyo]

michi=[]
for idx in range(0,N,1):
    michi.append([])

for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])
    michi[A].append((B,C))
    michi[B].append((A,C))


rCost=[]
for idr in range(0,R,1):
    Cost=[None]*N
    Cost[r[idr]]=0
    miru=[r[idr]]
    while miru:
        nextmiru=[]
        for toshi in miru:
            preCost=Cost[toshi]
            for (saki,sakiCost) in michi[toshi]:
                tmpCost=preCost+sakiCost
                if Cost[saki]==None or tmpCost < Cost[saki]:
                    Cost[saki]=tmpCost
                    nextmiru.append(saki)

        miru=list(set(nextmiru))
    rCost.append(Cost)

#for ko in rCost:
#    print(ko)

ans=None
search([])
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    mod = 10**9+7
    A, B = [], {}
    for i in range(n):
        d = {}
        for j in range(2,int(a[i]**0.5)+1):
            if a[i]%j==0:
                cnt = 0
                while a[i]%j==0:
                    cnt += 1
                    a[i] = a[i]//j
                d[j] = cnt
                if B.get(j)==None:
                    B[j] = cnt
                else:
                    if B[j]<cnt:
                        B[j] = cnt
        if a[i]!=1:
            d[a[i]] = 1
            if B.get(a[i])==None:
                B[a[i]] = 1
        A.append(d)
    ans = 0
    for i in range(n):
        d = A[i]
        a = 1
        for k in B.keys():
            if d.get(k)!=None:
                a *= pow(k,B[k]-d[k],mod)
            else:
                a *= pow(k,B[k],mod)
            a = a%mod
        ans += a
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import copy
    n = int(input())
    a = list(map(int,input().split()))
    A = copy.deepcopy(a)
    mod = 10**9+7
    l = {}
    for i in range(n):
        for j in range(2,int(a[i]**0.5)+1):
            if a[i]%j==0:
                cnt = 0
                while a[i]%j==0:
                    cnt += 1
                    a[i] = a[i]//j
                if l.get(j)==None:
                    l[j] = cnt
                else:
                    l[j] = max(cnt,l[j])
        if a[i]!=1:
            if l.get(a[i])==None:
                l[a[i]] = 1
    L = 1
    for k in l.keys():
        L *= pow(k,l[k],mod)
    L = L%mod
    ans = 0
    for i in range(n):
        ans += L * pow(A[i],mod-2,mod) % mod
        ans = ans % mod
    print(ans)

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

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

# １からNまでの値をもつサイコロを振ったときの期待値
def ex(x:int):
    return (x*(x+1)/2)/x

# 期待値のリストを作る
kitaichi = []
for i in range(len(p)):
    kitaichi.append(ex(p[i]))

# 期待値の最大値のリストを作る
kitaichi_goukei = []
for i in range(len(kitaichi)-k+1):
    kitaichi_goukei.append(sum(kitaichi[i:i+k]))

print (max(kitaichi_goukei))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ex = [1/2*(i+1) for i in p]
total = [0]

for i in range(N):
    total.append (total[i] + ex[i])

ans = 0
for i in range(N+1-K):
    tmp = total[i+K] - total[i]
    if ans < tmp:
        ans = tmp

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

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
lastcheck = -1
for i in a:
    if i == lastcheck:
        continue
    else:
        count_of_i = a.count(i)
        if count_of_i < i:
            ans += count_of_i
        else:
            ans += count_of_i - i
        lastcheck = i
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
counter = Counter(a)
for i in set(a):
    if counter[i] < i:
        ans += counter[i]
    else:
        ans += counter[i] - i
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if i[1] == "1":
      if c==0:
        s = i[2] + s
      else:
        s = s + i[2] 
    else:
      if c==1:
        s = i[2] + s
      else:
        s = s + i[2] 
if c == 1:
  s = ''.join(list(reversed(s)))
print(s)

### FIXED CODE ###

from collections import deque

s = deque( list(input()) )
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if (c+int(i[1]))%2 ==1:
      s.appendleft(i[2])
    else:
      s.append(i[2])

s=list(s)

if c == 1:
  s.reverse()

s = ''.join(s)
print(s)
### BUGGY CODE ###

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

ret = 10**10

for leader in range(len(S)):
    leftW = S[0:leader].count("W")
    rightE = S[leader+1:len(S)].count("E")
    # print("{}, {}".format(leftW, rightE))
    sum = leftW + rightE
    ret = min(ret, sum)

print(ret)


### FIXED CODE ###

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

W = [0] * (N+2)
E = [0] * (N + 2)

s = 0
e = 0
for i in range(0, N):
    if S[i] == "W":
        s += 1
    else:
        e += 1
    W[i + 1] = s
    E[i + 1] = e

ret = 10**10
for leader in range(1, N+1):
    leftW = W[leader-1]
    rightE = E[N]-E[leader]
    # print("{}, {}".format(leftW, rightE))
    sum = leftW + rightE
    ret = min(ret, sum)

print(ret)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

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

# dp[i][j], i:step, j:path
from collections import Counter, defaultdict
parents = Counter( x[0] for x in g)
childs  = Counter( x[1] for x in g)


childs_list  = defaultdict(list)
for x,y in g:
    childs_list[x].append(y)


roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

# root = i
l =  [ (i,childs_list[i], 0) for i in roots]
# l = [ (i, childs_list[i], 0) ] 
ans = 0
while l: 
    v_idx, chlist, cnt = l.pop()
    ans = max(ans, cnt)
    for c in sorted(chlist, key=lambda x:childs[x]):
        l.append(  (c, childs_list[c], cnt+1) ) 
print(ans)
        
        



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 

    nex_stack = []
    # p = l.pop()
    for p in l:
        # cnt = costs[p]
        for c in childs_list[p]:
            costs[c] = max(costs[p]+1, costs[c])
            childs[c] -= 1
            if childs[c] == 0:
                nex_stack.append(c)
    
    l = nex_stack


print(max(costs))
### BUGGY CODE ###

import heapq
import math
n,m = map(int,input().split())
lst = list(map(int,input().split()))
lst = list(map(lambda x:x*(-1),lst))
heapq.heapify(lst)
for i in range(m):
    num = heapq.heappop(lst)
    num = math.ceil(num / 2)
    heapq.heappush(lst,num)
    if sum(lst) == 0:
        break
print(sum(lst) * (-1))

### FIXED CODE ###

import heapq
import math
n,m = map(int,input().split())
lst = [int(x) * (-1) for x in input().split()]
heapq.heapify(lst)
for use_cnt in range(m):
    num = heapq.heappop(lst) * -1
    nxt_num = math.floor(num / 2)
    heapq.heappush(lst,nxt_num * -1)
print(sum(lst) * (-1))
### BUGGY CODE ###

#ABC179-d
import sys,math,collections,itertools
input = sys.stdin.readline
m=998244353

N,K=list(map(int,input().split()))
DP = [0]*(2*10**5+1)
move = []
for _ in range(K):
    l,r=list(map(int,input().split()))
    move += list(range(l,r+1))
move.sort()
ans = 0
for i in range(2,N+1):
    for mo in move:
        if i-mo<=0:
            break
        elif i-mo==1:
            DP[i]+=1
        else:
            DP[i]+=DP[i-mo]
print(DP[N]%m)
        


### FIXED CODE ###

N,K = map(int,input().split())
DP = [0]*(N+1)
DPsum=[0]*(N+1)
DP[1]=1
DPsum[1]=1
lr = []
m=998244353
for _ in range(K):
    l,r = map(int,input().split())
    lr.append([l,r])

for i in range(2,N+1):
    for l,r in lr:
        lx = i - r - 1
        rx = i - l
        lx = max(0,lx)
        rx = max(0,rx)
        DP[i]+= DPsum[rx]-DPsum[lx]
    DPsum[i]=(DPsum[i-1]+DP[i])%m
print(DP[N]%m)
### BUGGY CODE ###

N = int(input())
d = list(map(int, input().split()))
for j in range(1, N+1):
    count = 0
    for i in range(len(d)):
        if j == d[i]:
            count += 1
    print(count)

### FIXED CODE ###

N = int(input())
d = list(map(int, input().split()))
p = [0] * N
for i in range(N - 1):
    p[d[i] - 1] += 1
for i in range(N):
    print(p[i])
### BUGGY CODE ###


NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
candidate_list = [0] * (N-1)
tree_dict = {}
#Make tree dict
for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])
    tree_dict[i+1] = {
                'count': 0,
                'has_trees': []
            }
    candidate_list[N-2-i] = (a,b)
tree_dict[N] = {
    'count': 0,
    'has_trees': []
    }
for candidate in candidate_list:
    a = candidate[0]
    b = candidate[1]
    tree_dict[a]['has_trees'] += tree_dict[b]['has_trees'] + [b]
        

for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    tree_dict[p]['count'] += x
    for num in tree_dict[p]['has_trees']:
        tree_dict[num]['count'] += x

out_put_list = []
for each_dict in tree_dict.values():
    out_put_list.append(str(each_dict['count']))
print(' '.join(out_put_list))

### FIXED CODE ###


NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
out_put_list = [0] * N
tree_list = {}
for i in range(N):
    tree_list[i] = []

for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0]) -1
    b = int(ab[1]) -1
    tree_list[a].append(b)

for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    out_put_list[p-1] += x

for i in range(len(tree_list)):
    for num in tree_list[i]:
        out_put_list[num] += out_put_list[i]

print(*out_put_list)
### BUGGY CODE ###

N = int(input())
l = [0]*(10**5+1)
A = list(map(int,input().split()))
Q = int(input())
for a in A:
  l[a] += a

for _ in range(Q):
  b,c = map(int,input().split())
  l[c] += (l[b]//b)*c
  l[b] = 0
  print(sum(l))

### FIXED CODE ###

N = int(input())
l = [0]*(10**5+1)
A = list(map(int,input().split()))
Q = int(input())
for a in A:
  l[a] += a
suml = sum(l)
for _ in range(Q):
  b,c = map(int,input().split())
  suml += ((l[b]//b)*c - l[b])
  l[c] += (l[b]//b)*c
  l[b] = 0
  print(suml)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math

in_a = list(map(int, input().split()))
A = in_a[0]
B = in_a[1]
N = in_a[2]

ans = 0

if ( B>N ):
  X = N
  ans = math.floor(A*X/B) - ( A * math.floor(X/B) )
  
else:
  M = math.floor( (N/B)+1 )
  for i in range(M):
    X = ( i * M ) - 1
    temp = math.floor(A*X/B) - ( A * math.floor(X/B) )
    if ( temp>ans ):
      ans = temp

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

in_a = list(map(int, input().split()))
A = in_a[0]
B = in_a[1]
N = in_a[2]

ans = 0

if ( B>N ):
  X = N
  ans = math.floor(A*X/B) - ( A * math.floor(X/B) )
  
else:
  X = B - 1
  ans = math.floor(A*X/B) - ( A * math.floor(X/B) )

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

n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]

s, t = a[0][0], a[0][1]

for i in range(1, n):
    if a[i][0] < a[i][1]:
        j = 1
        while True:
            if a[i][0]*j < s or a[i][1]*j < t:
                pass
            else:
                s = a[i][0]*j
                break
            j += 1

        t = j*a[i][1]

    elif a[i][0] > a[i][1]:
        j = 1
        while True:
            if a[i][1]*j < t or a[i][0]*j < s:
                pass
            else:
                t = a[i][1]*j
                break
            j += 1

        s = j*a[i][0]

    else:
        s, t = max(s, t), max(s,t)

print(s+t)



### FIXED CODE ###

n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]

s, t = 1, 1
for i in range(0, n):

    j = max((s+a[i][0]-1)//a[i][0], (t+a[i][1]-1)//a[i][1])
    s, t = a[i][0]*j, a[i][1]*j

print(s+t)
### BUGGY CODE ###

from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



while query:
    lq,rq,j=query.pop()   
    ans[j]=rq-lq+1-(seg.get(lq-1,rq))
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


### FIXED CODE ###

from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)
### BUGGY CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)
    items = [(next(data), next(data)) for _ in range(N)]
    Q = next(data)

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    dp = [None for _ in range(H)]
    dp[0] = [0] * (MX + 1)
    for i in range(1, H):
        v, w = items[i - 1]
        dpip = dp[i >> 1]
        dpi = dpip[:]
        dp[i] = dpi
        for j in range(w, MX + 1):
            dpi[j] = max(dpi[j], dpip[j - w] + v)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue
        ans = 0
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    iv, iw = items[node - 1]
                    value += iv
                    weight += iw
                node >>= 1
                i >>= 1
            if weight > L:
                continue
            ans = max(ans, value + dp[node][L - weight])
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

if __name__ == '__main__':
    main()