CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    M = 2**12
    N = int(eval(input()))
    V = []
    W = []
    for i in range(N):
        v,w = list(map(int,input().split()))
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)

    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    memo = {}
    def rec(n,l):
        if n < M:
            return dp[n][l]
        elif (n,l) in memo:
            return memo[(n,l)]
        else:
            c = 0
            if l>=W[n-1]:
                c = rec(n//2,l-W[n-1])+V[n-1]
            res = max(rec(n//2,l),c)
            memo[(n,l)] = res
            return res

    Q = int(eval(input()))
    vL = [list(map(int,input().split())) for _ in range(Q)]

    for i in range(Q):
        v,L = vL[i]
        print((rec(v,L)))

if __name__ == '__main__':
    main()

# Optimized solution
def main():
    M = 2**11
    N = int(eval(input()))
    V = []
    W = []
    for i in range(N):
        v,w = list(map(int,input().split()))
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)

    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    memo = {}
    def rec(n,l):
        if n < M:
            return dp[n][l]
        elif (n,l) in memo:
            return memo[(n,l)]
        else:
            c = 0
            if l>=W[n-1]:
                c = rec(n//2,l-W[n-1])+V[n-1]
            res = max(rec(n//2,l),c)
            memo[(n,l)] = res
            return res

    Q = int(eval(input()))
    vL = [list(map(int,input().split())) for _ in range(Q)]

    for i in range(Q):
        v,L = vL[i]
        print((rec(v,L)))

if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline

N = int(eval(input()))
VW = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
Q = int(eval(input()))
vL = [list(map(int,input().split())) for i in range(Q)]
vs,Ls = list(zip(*vL))

appear = []
for v in vs:
    v *= 2
    while v:
        v //= 2
        appear.append(v)

appear = sorted(list(set(appear)))
M = len(appear)+1
dic = {v:i for i,v in enumerate(appear)}

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

maxL = max(Ls)
dp = dpinit((M+1,maxL + 2),0)
ans = []

visited = [False] * (M+1)
visited[0] = True
for v,L in vL:
    orgv = v
    seq = []
    v *= 2
    while v:
        v //= 2
        seq.append(v)
        rv = dic[v]
        if visited[rv]:
            break
        visited[rv] = True
    seq = seq[::-1]
    for s,ns in zip(seq,seq[1:]):
        V,W = VW[ns]
        s = dic[s]
        ns = dic[ns]
        for i in range(W):
            dp[ns][i] = dp[s][i]
        for i in range(W,maxL+2):
            dp[ns][i] = max(dp[s][i], dp[s][i-W] + V)
    ans.append(dp[orgv][L])

for a in ans:
    print(a)









# Optimized solution
import sys
lines = sys.stdin.readlines()

#N = int(input())
#VW = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
#Q = int(input())
#vL = [list(map(int,input().split())) for i in range(Q)]
#vs,Ls = zip(*vL)

N = int(lines[0])
Q = int(lines[N+1])
vL = [list(map(int,s.split())) for s in lines[N+2:]]
vs,Ls = list(zip(*vL))
VW = {}

appear = []
for v in vs:
    v *= 2
    while v:
        v //= 2
        appear.append(v)

appear = list(set(appear))
M = len(appear)+1
dic = {v:i for i,v in enumerate(appear)}

for v in appear:
    VW[dic[v]] = list(map(int, lines[v].split()))

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

maxL = max(Ls)
dp = dpinit((M+1,maxL+2),0)
ans = []

visited = [False] * (M+1)
visited[0] = True
for v,L in vL:
    orgv = v
    seq = []
    v *= 2
    while v:
        v //= 2
        seq.append(v)
        rv = dic[v]
        if visited[rv]:
            break
        visited[rv] = True
    seq = seq[::-1]
    for s,ns in zip(seq,seq[1:]):
        s = dic[s]
        ns = dic[ns]
        V,W = VW[ns]
        for i in range(W):
            dp[ns][i] = dp[s][i]
        for i in range(W,maxL+2):
            dp[ns][i] = max(dp[s][i], dp[s][i-W] + V)
    ans.append(dp[dic[orgv]][L])

for a in ans:
    print(a)
# Original solution
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        d_ = dp[(i+1)>>1][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
        V.append(v)
        W.append(w)
        dp.append(d_)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print((dp[v][L]))
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print((dp[v][L]))
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()
# Original solution
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print((dp[v][L]))
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print((dp[v][L]))
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()
# Original solution
import copy

n = int(eval(input()))
size = 100001
vw = []
for i in range(n):
    V, w = list(map(int, input().split()))
    vw.append([V, w])
status = [False] * (n + 1)
status[0] = [-1] * size
status[0][0] = 0
q = int(eval(input()))
for i in range(q):
    v, l = list(map(int, input().split()))
    root = [v]
    while root[-1] != 1:
        root.append(root[-1] // 2)
    root.reverse()
    for j in root:
        v0, w0 = vw[j-1][0], vw[j-1][1]
        if status[j] == False:
            temp = copy.copy(status[j//2])
            for k in range(len(temp) - w0):
                p = len(temp) - k - w0 - 1
                q = len(temp) - k - 1
                if temp[p] != -1:
                    temp[q] = max(temp[q], temp[p] + v0)
            status[j] = temp
        else:
            pass
    temp2 = status[v][:l + 1]
    print((max(temp2)))

# Optimized solution
import copy

n = int(eval(input()))
size = 100001
vw = []
for i in range(n):
    V, w = list(map(int, input().split()))
    vw.append([V, w])
status = [False] * (n + 1)
status[0] = {0:0}
q = int(eval(input()))
for i in range(q):
    v, l = list(map(int, input().split()))
    root = [v]
    while root[-1] != 1:
        root.append(root[-1] // 2)
    root.reverse()
    for j in root:
        v0, w0 = vw[j-1][0], vw[j-1][1]
        if status[j] == False:
            temp = copy.copy(status[j//2])
            keys = list(temp.keys())
            keys.sort(reverse = True)
            for k in keys:
                if k + w0 in keys:
                    temp[k + w0] = max(temp[k + w0], temp[k] + v0)
                else:
                    temp[k + w0] = temp[k] + v0
            status[j] = temp
        else:
            pass
    temp2 = status[v]
    values = [temp2[i] for i in list(temp2.keys()) if i <= l]
    print((max(values)))
# Original solution
import sys

n, *inp = list(map(int, sys.stdin.buffer.read().split()))
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 11, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print(('\n'.join(map(str, buf))))


# Optimized solution
import sys


def get_solve():
    cache = [None] * precalc_limit
    cache[0] = [0] * (weight_limit + 1)
    _vvv = vvv
    _www = www
    _weight_limit = weight_limit

    def _f(u):
        """ u < precalc_limit """
        if cache[u] is not None:
            return cache[u]
        dp = _f(u >> 1).copy()
        v = _vvv[u]
        w = _www[u]
        for x in range(_weight_limit, w - 1, -1):
            nv = dp[x - w] + v
            if dp[x] < nv:
                dp[x] = nv
        cache[u] = dp
        return dp

    return _f


n, *inp = list(map(int, sys.stdin.buffer.read().split()))
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)

solve = get_solve()

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        dp = solve(u)
        buf.append(dp[l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    dp = solve(u)
    for w, v in zip(dp_w, dp_v):
        nv = v + dp[l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print(('\n'.join(map(str, buf))))
# Original solution
import sys
input=sys.stdin.buffer.readline

N=int(eval(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[v][m-1][0]
        temp[i][1]=temp[i-2**(m-1)][1]+data[v][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(eval(input()))):
    v,L=list(map(int,input().split()))
    print((solve(v,L)))


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

start=time.time()
N=int(eval(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(eval(input()))
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=list(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]))
# Original solution
import sys
sys.setrecursionlimit(10**9)
import sys
input = sys.stdin.readline

n=int(eval(input()))
vw=[list(map(int,input().split())) for _ in range(n)]
q=int(eval(input()))
vl=[list(map(int,input().split())) for _ in range(q)]
#import numpy as np
#dp=np.full((n+1,10**5+1),-1,int)
dp=[[-1]*(10**5+1) for _ in range(n+1)]
#dp[:,0]=0
#dp[1,:vw[0][1]]=0
#dp[1,vw[0][1]:]=vw[0][0]
def func(i,l):
  if l==0:
    return 0
  if i==1:
    if l>=vw[0][1]:
      return vw[0][0]
    else:
      return 0
  if dp[i][l]>-1:
    return dp[i][l]
  v,w=vw[i-1]
  ret=0
  ret=max(func(i//2,l),func(i//2,l-w)+v if l-w>=0 else 0)
  dp[i][w]=ret
  return ret
for v,l in vl:
  print((func(v,l)))

# Optimized solution
import sys
sys.setrecursionlimit(10**9)
import sys
input = sys.stdin.readline

n=int(eval(input()))
vw=[list(map(int,input().split())) for _ in range(n)]
q=int(eval(input()))
vl=[list(map(int,input().split())) for _ in range(q)]
from collections import defaultdict
dp=defaultdict(lambda:-1)
#dp=[[-1]*(10**5+1) for _ in range(n+1)]
def func(i,l):
  if l==0:
    return 0
  if i==1:
    if l>=vw[0][1]:
      return vw[0][0]
    else:
      return 0
  if dp[(i,l)]>-1:
    return dp[(i,l)]
  v,w=vw[i-1]
  ret=0
  ret=max(func(i//2,l),func(i//2,l-w)+v if l-w>=0 else 0)
  dp[(i,w)]=ret
  return ret
for v,l in vl:
  print((func(v,l)))
# Original solution
N=int(eval(input()))
V=[]
W=[]
S=10**5
D=[[0]*(S+1) for _ in range(N+1)] #D[x][k]:wまで,重さw以下

for i in range(N):
    v,w=list(map(int,input().split()))
    V.append(v)
    W.append(w)

for x in range(1,N+1):
    for w in range(S+1):
        if w>=W[x-1]:
            D[x][w]=max(D[x>>1][w],D[x>>1][w-W[x-1]]+V[x-1])
        else:
            D[x][w]=D[x>>1][w]
            
Q=int(eval(input()))
for _ in range(Q):
    v,L=list(map(int,input().split()))
    print((D[v][L]))


# Optimized solution
from  math import ceil,log

N=int(eval(input()))
V=[]
W=[]
S=100

for i in range(N):
    v,w=list(map(int,input().split()))
    V.append(v)
    W.append(w)
            
Q=int(eval(input()))
for _ in range(Q):
    v,L=list(map(int,input().split()))
    d=ceil(log(v+1,2))
    D=[[0]*(L+1) for _ in range(d+1)]

    w=v
    E=[]
    while w!=0:
        E.append(w)
        w=w>>1
    
    for i in range(1,d+1):
        for w in range(L+1):
            if w>=W[E[-i]-1]:
                D[i][w]=max(D[i-1][w],D[i-1][w-W[E[-i]-1]]+V[E[-i]-1])
            else:
                D[i][w]=D[i-1][w]

    print((D[-1][-1]))
# Original solution
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())
n, = list(map(int,readline().split()))
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

#print(vw)
A = 11
N = min(1<<A,n+1)

memo = [[0] for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

from itertools import accumulate

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = list(accumulate(m,max))


q, = list(map(int,readline().split()))
for _ in range(q):
    u,l = list(map(int,readline().split()))

    dic = [(0,0)]
    while u >= N:
        dic += [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic]
        u >>= 1
    
    ans = 0
    for w,v in dic:
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

        


# Optimized solution
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

n, = list(map(int,readline().split()))
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 2
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]

#from itertools import acumulate
for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    #memov[i] = list(accumulate(memov[i],max))
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    #print(lstv,lstw,dv,dw,l)
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = list(map(int,readline().split()))
for _ in range(q):
    u,l = list(map(int,readline().split()))

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    #for j in range(1,len(dv)):
    #    dv[j] = max(dv[j-1],dv[j])
    
    solve(memov[u],memow[u],dv,dw,l)

#print(memov)
#print(memow)
# Original solution
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())
n, = list(map(int,readline().split()))
vw = [(0,0)]+[tuple(map(int,readline().split())) for _ in range(n)]

A = 10
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m

q, = list(map(int,readline().split()))
for _ in range(q):
    u,l = list(map(int,readline().split()))

    dv = [0]
    dw = [0]
    while u >= N:
        dv += [vw[u][0]+v1 for v1 in dv]
        dw += [vw[u][1]+w1 for w1 in dw]
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

        


# Optimized solution
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())
n, = list(map(int,readline().split()))
vw = [(0,0)]+[tuple(map(int,readline().split())) for _ in range(n)]

A = 10
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m

q, = list(map(int,readline().split()))
for _ in range(q):
    u,l = list(map(int,readline().split()))

    m = u.bit_length() - A
    if m<0: m=0
    dv = [0]*(1<<m)
    dw = [0]*(1<<m)
    for i in range(m):
        v,w = vw[u]
        for j in range(1<<i):
            dv[j+(1<<i)] = dv[j]+v
            dw[j+(1<<i)] = dw[j]+w
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)