Problem p02648 (python)

Fixed submission:
#!/usr/bin/env python3
import sys

#solve
def solve():

    input = sys.stdin.buffer.readline
    LI = lambda: map(int, input().split())
    II = lambda: int(input())
    n = II()
    vw = [[]] * n
    M = 10 ** 5 + 1
    M0 = [0] * M
    XX = 1 << 10
    d = [[]] * XX
    d[0] = M0

    for i in range(1, min(XX, n + 1)):
        v, w = LI()
        vw[i - 1] = (v, w)
        di = d[i // 2][:]
        for j in range(M - 1, w - 1, -1):
            if di[j] < di[j - w] + v:
                di[j] = di[j - w] + v
        d[i] = di

    for i in range(XX, n + 1):
        v, w = LI()
        vw[i - 1] = (v, w)

    Vv = [i.bit_length() for i in range(1 << 18)]
    n = [pow(2, i) for i in range(18)]
    lentl = [i - 10 for i in range(19)]
    maskset = [[]] * n[10]

    for i in range(1, 11):
        for mask in range(n[i - 1], n[i]):
            a = mask & -mask
            b = Vv[a] - 1
            maska = mask - a
            maskset[mask - 1] = (mask, b, maska)

    for _ in range(II()):
        V, L = LI()

        if V < XX:
            print(d[V][L])
            continue

        n2 = lentl[Vv[V]]
        vw2 = [None] * n2

        for i in range(n2):
            vw2[i] = (vw[V - 1][0], vw[V - 1][1])
            V //= 2

        lw = [0] * n[n2]
        lv = [0] * n[n2]
        dv = d[V]
        ans = dv[L]

        for i in range(n[n2] - 1):
            mask, b, maska = maskset[i]
            v, w = vw2[b]
            ww = lw[maska] + w
            Lww = L - ww
            lw[mask] = ww
            if Lww < 0: continue
            vv = lv[maska] + v
            lv[mask] = vv
            tmp = dv[Lww] + vv
            if tmp > ans:
                ans = tmp
        print(ans)
    return

if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys

#solve
def solve():

    input = sys.stdin.buffer.readline
    LI = lambda: map(int, input().split())
    II = lambda: int(input())
    n = II()
    vw = [[]] * n
    M = 10 ** 5 + 1
    M0 = [0] * M
    XX = 1 << 9
    d = [[]] * XX
    d[0] = M0

    for i in range(1, min(XX, n + 1)):
        v, w = LI()
        vw[i - 1] = (v, w)
        di = d[i // 2][:]
        for j in range(M - 1, w - 1, -1):
            if di[j] < di[j - w] + v:
                di[j] = di[j - w] + v
        d[i] = di

    for i in range(XX, n + 1):
        v, w = LI()
        vw[i - 1] = (v, w)

    Vv = [i.bit_length() for i in range(n + 1)]
    n = [pow(2, i) for i in range(18)]
    lentl = [i - 9 for i in range(19)]
    maskset = [[]] * n[9]

    for i in range(1, 10):
        for mask in range(n[i - 1], n[i]):
            a = mask & -mask
            b = Vv[a] - 1
            maska = mask - a
            maskset[mask - 1] = (mask, b, maska)

    for _ in range(II()):
        V, L = LI()

        if V < XX:
            print(d[V][L])
            continue

        n2 = lentl[Vv[V]]
        vw2 = [None] * n2

        for i in range(n2):
            vw2[i] = (vw[V - 1][0], vw[V - 1][1])
            V //= 2

        lw = [0] * n[n2]
        lv = [0] * n[n2]
        dv = d[V]
        ans = dv[L]

        for i in range(n[n2] - 1):
            mask, b, maska = maskset[i]
            v, w = vw2[b]
            ww = lw[maska] + w
            Lww = L - ww
            lw[mask] = ww
            if Lww < 0: continue
            vv = lv[maska] + v
            lv[mask] = vv
            tmp = dv[Lww] + vv
            if tmp > ans:
                ans = tmp
        print(ans)
    return

if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys

#solve
def solve():

    input = sys.stdin.buffer.readline
    LI = lambda: map(int, input().split())
    II = lambda: int(input())
    n = II()
    vw = [[]] * n
    M = 10 ** 5 + 1
    M0 = [0] * M
    XX = 1 << 9
    d = [[]] * XX
    d[0] = M0

    for i in range(1, min(XX, n + 1)):
        v, w = LI()
        vw[i - 1] = (v, w)
        di = d[i // 2][:]
        for j in range(M - 1, w - 1, -1):
            if di[j] < di[j - w] + v:
                di[j] = di[j - w] + v
        d[i] = di

    for i in range(XX, n + 1):
        v, w = LI()
        vw[i - 1] = (v, w)

    vv = [i.bit_length() for i in range(n + 1)]
    n = [pow(2, i) for i in range(18)]
    lentl = [i - 9 for i in range(19)]
    maskset = [[]] * n[9]

    for i in range(1, 10):
        for mask in range(n[i - 1], n[i]):
            a = mask & -mask
            b = a.bit_length() - 1
            maska = mask - a
            maskset[mask - 1] = (mask, b, maska)

    for _ in range(II()):
        V, L = LI()

        if V < XX:
            print(d[V][L])
            continue

        n2 = lentl[vv[v]]
        vw2 = [None] * n2

        for i in range(n2):
            vw2[i] = (vw[V - 1][0], vw[V - 1][1])
            V //= 2

        lw = [0] * n[n2]
        lv = [0] * n[n2]
        dv = d[V]
        ans = dv[L]

        for i in range(n[n2] - 1):
            mask, b, maska = maskset[i]
            v, w = vw2[b]
            ww = lw[maska] + w
            Lww = L - ww
            lw[mask] = ww
            if Lww < 0: continue
            vv = lv[maska] + v
            lv[mask] = vv
            tmp = dv[Lww] + vv
            if tmp > ans:
                ans = tmp
        print(ans)
    return

if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys

#solve
def solve():
    input = sys.stdin.buffer.readline
    LI = lambda: map(int, input().split())
    II = lambda: int(input())
    n = II()
    vw = [[]] * n
    nbit = 1 << n.bit_length()
    M = 10 ** 5 + 1
    M0 = [0] * M
    XX = 1 << n.bit_length() // 2
    d = [[]] * XX
    d[0] = M0
    for i in range(1, XX):
        v, w = LI()
        vw[i - 1] = (v, w)
        di = d[i // 2][:]
        for j in range(M - 1, w - 1, -1):
            if di[j] < di[j - w] + v:
                di[j] = di[j - w] + v
        d[i] = di
    for i in range(XX, n + 1):
        v, w = LI()
        vw[i - 1] = (v, w)
    n = [pow(2, i) for i in range(18)]
    lentl = [i - i // 2 for i in range(18)]
    for _ in range(II()):
        V, L = LI()
        n2 = lentl[V.bit_length()]
        if V < XX:
            print(d[V][L])
            continue
        vw2 = [None] * n2
        for i in range(n2):
            vw2[i] = (vw[V - 1][0], vw[V - 1][1])
            V //= 2
        lw = [0] * n[n2]
        lv = [0] * n[n2]
        dv = d[V]
        ans = dv[L]
        for mask in range(1, n[n2]):
            a = mask & -mask
            b = a.bit_length() - 1
            v, w = vw2[b]
            maska = mask - a
            ww = lw[maska] + w
            Lww = L - ww
            lw[mask] = ww
            if Lww < 0: continue
            vv = lv[maska] + v
            lv[mask] = vv
            tmp = dv[Lww] + vv
            if tmp > ans:
                ans = tmp
        print(ans)
    return

if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
LI = lambda:map(int, input().split())
II = lambda:int(input())

#solve
def solve():
    n = II()
    vw = []
    nbit = 1 << n.bit_length()
    M = 10 ** 5 + 1
    M0 = [0] * M
    d = [M0]
    dp = [[]]
    XX = 1 << n.bit_length() // 2
    for _ in range(1, XX):
        v, w = LI()
        vw.append((v, w))
        di = d[i // 2][:]
        for j in range(M - 1, w - 1, -1):
            if di[j] < di[j - w] + v:
                di[j] = di[j - w] + v
        d.append(di)
    for _ in range(XX, n + 1):
        v, w = LI()
        vw.append((v, w))
    n = [pow(2, i) for i in range(18)]
    for _ in range(II()):
        V, L = LI()
        lent = V.bit_length()
        if V < XX:
            print(d[V][L])
            continue
        n1 = lent // 2
        n2 = lent - n1
        vw2 = []
        for _ in range(n2):
            vw2.append((vw[V - 1][0], vw[V - 1][1]))
            V //= 2
        lw = [0] * n[n2]
        lv = [0] * n[n2]
        dv = d[V]
        ans = dv[L]
        for mask in range(1, n[n2]):
            a = mask & -mask
            b = a.bit_length() - 1
            v, w = vw2[b]
            maska = mask - a
            ww = lw[maska] + w
            Lww = L - ww
            lw[mask] = ww
            if Lww < 0: continue
            vv = lv[maska] + v
            lv[mask] = vv
            if dv[Lww] + vv > ans:
                ans = dv[Lww] + vv
        print(ans)
    return


solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
LI = lambda:map(int, input().split())
II = lambda:int(input())

#solve
def solve():
    n = II()
    vw = []
    nbit = 1 << n.bit_length()
    M = 10 ** 5 + 1
    M0 = [0] * M
    d = [M0]
    for i in range(n):
        v, w = LI()
        vw.append((v, w))
    dp = [[]]
    for i in range(1, 1 << n.bit_length() // 2):
        di = M0[:]
        n2 = i.bit_length()
        lw = [0] * (1 << n2)
        lv = [0] * (1 << n2)
        dpi = dp[i // 2][:]
        dpi.append((vw[i - 1][0], vw[i - 1][1]))
        for mask in range(1, 1 << n2):
            a = mask & -mask
            b = a.bit_length() - 1
            v, w = dpi[b]
            ww = lw[mask - a] + w
            lw[mask] = ww
            if ww >= M: continue
            vv = lv[mask - a] + v
            lv[mask] = vv
            if di[ww] < vv:
                di[ww] = vv
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
        d.append(di)
    for _ in range(II()):
        V, L = LI()
        lent = V.bit_length()
        n1 = lent // 2
        n2 = lent - n1
        vw2 = []
        for _ in range(n2):
            vw2.append((vw[V - 1][0], vw[V - 1][1]))
            V //= 2
        lw = [0] * (1 << n2)
        lv = [0] * (1 << n2)
        dv = d[V]
        ans = dv[L]
        for mask in range(1, 1 << n2):
            a = mask & -mask
            b = a.bit_length() - 1
            v, w = vw2[b]
            ww = lw[mask - a] + w
            lw[mask] = ww
            if ww > L: continue
            vv = lv[mask - a] + v
            lv[mask] = vv
            if dv[L - ww] + vv > ans:
                ans = dv[L - ww] + vv
        print(ans)
    return


solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
def LI(): return map(int, input().split())
def II(): return int(input())

#solve
def solve():
    n = II()
    v,w = LI()
    nbit = 1 << n.bit_length()
    dp = [[]] * (nbit)
    dp[1] = [(v, w)]
    for i in range(1, nbit >> 1):
        dpi = dp[i]
        if 2 * i + 1 <= n:
            v0, w0 = LI()
            v1, w1 = LI()
            dp21 = dpi[:]
            dp20 = dpi[:]
            dp21.append((v1, w1))
            dp20.append((v0, w0))
            dp[2 * i + 1] = dp21
            dp[2 * i] = dp20
        elif 2 * i <= n:
            v0, w0 = LI()
            dp20 = dpi[:]
            dp20.appned((v0, w0))
            dp[2 * i] = dp20
        else:
            break
    return
    M = 10 ** 5 + 1
    M0 = [0] * M
    d = [M0]
    for i in range(1, 1 << n.bit_length() // 2):
        d1 = defaultdict(int)
        d1[0] = 0
        di = M0[:]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                keyw = key + w
                valuev = value + v
                if keyw >= M: continue
                if d1[keyw] < valuev:
                    d1[keyw] = valuev
                    di[keyw] = valuev
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
        d.append(di)
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        lent = V.bit_length()
        n1 = lent // 2
        n2 = lent - n1
        vw2 = t[n1:]
        V = V >> n2
        lw = [0] * (1 << n2)
        lv = [0] * (1 << n2)
        dv = d[V]
        ans = dv[L]
        for mask in range(1, 1 << n2):
            a = mask & -mask
            b = a.bit_length() - 1
            v, w = vw2[b]
            ww = lw[mask - a] + w
            lw[mask] = ww
            if ww > L: continue
            vv = lv[mask - a] + v
            lv[mask] = vv
            if dv[L - ww] + vv > ans:
                ans = dv[L - ww] + vv
        print(ans)
    return


solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
def LI(): return map(int, input().split())
def II(): return int(input())

#solve
def solve():
    n = II()
    v,w = LI()
    nbit = 1 << n.bit_length()
    dp = [[]] * (nbit)
    dp[1] = [(v, w)]
    for i in range(1, nbit >> 1):
        dpi = dp[i]
        if 2 * i + 1 <= n:
            v0, w0 = LI()
            v1, w1 = LI()
            dp21 = dpi[:]
            dp20 = dpi[:]
            dp21.append((v1, w1))
            dp20.append((v0, w0))
            dp[2 * i + 1] = dp21
            dp[2 * i] = dp20
        elif 2 * i <= n:
            v0, w0 = LI()
            dp20 = dpi[:]
            dp20.appned((v0, w0))
            dp[2 * i] = dp20
        else:
            break
    M = 10 ** 5 + 1
    M0 = [0] * M
    d = [M0]
    for i in range(1, 1 << n.bit_length() // 2):
        d1 = defaultdict(int)
        d1[0] = 0
        di = M0[:]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                keyw = key + w
                valuev = value + v
                if keyw >= M: continue
                if d1[keyw] < valuev:
                    d1[keyw] = valuev
                    di[keyw] = valuev
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
        d.append(di)
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        lent = V.bit_length()
        n1 = lent // 2
        n2 = lent - n1
        vw2 = t[n1:]
        V = V >> n2
        lw = [0] * (1 << n2)
        lv = [0] * (1 << n2)
        dv = d[V]
        ans = dv[L]
        for mask in range(1, 1 << n2):
            a = mask & -mask
            b = a.bit_length() - 1
            v, w = vw2[b]
            ww = lw[mask - a] + w
            lw[mask] = ww
            if ww > L: continue
            vv = lv[mask - a] + v
            lv[mask] = vv
            if dv[L - ww] + vv > ans:
                ans = dv[L - ww] + vv
        print(ans)
    return


solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
def LI(): return map(int, input().split())
def II(): return int(input())

#solve
def solve():
    n = II()
    v,w = LI()
    nbit = 1 << n.bit_length()
    dp = [[]] * (nbit)
    dp[1] = [(v, w)]
    for i in range(1, nbit >> 1):
        dpi = dp[i]
        if 2 * i + 1 <= n:
            v0, w0 = LI()
            v1, w1 = LI()
            dp21 = dpi[:]
            dp20 = dpi[:]
            dp21.append((v1, w1))
            dp20.append((v0, w0))
            dp[2 * i + 1] = dp21
            dp[2 * i] = dp20
        elif 2 * i <= n:
            v0, w0 = LI()
            dp20 = dpi[:]
            dp20.appned((v0, w0))
            dp[2 * i] = dp20
        else:
            break
    M = 10 ** 5 + 1
    M0 = [0] * M
    d = [M0]
    for i in range(1, 1 << n.bit_length() // 2):
        d1 = defaultdict(int)
        d1[0] = 0
        di = M0[:]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                keyw = key + w
                valuev = value + v
                if keyw >= M: continue
                if d1[keyw] < valuev:
                    d1[keyw] = valuev
                    di[keyw] = valuev
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
        d.append(di)
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        lent = V.bit_length()
        n1 = lent // 2
        n2 = lent - n1
        vw2 = t[n1:]
        V = V >> n2
        d1 = defaultdict(int)
        d1[0] = 0
        dv = d[V]
        ans = dv[L]
        for v, w in vw2:
            for key, value in list(d1.items()):
                keyw = key + w
                if keyw > L: continue
                valuev = value + v
                if d1[keyw] < valuev:
                    d1[keyw] = valuev
                    if dv[L - keyw] + valuev > ans:
                        ans = dv[L - keyw] + valuev
        print(ans)
    return


solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
def LI(): return map(int, input().split())
def II(): return int(input())

#solve
def solve():
    n = II()
    v,w = LI()
    nbit = 1 << n.bit_length()
    dp = [[]] * (nbit)
    dp[1] = [(v, w)]
    for i in range(1, nbit >> 1):
        dpi = dp[i]
        if 2 * i + 1 <= n:
            v0, w0 = LI()
            v1, w1 = LI()
            dp21 = dpi[:]
            dp20 = dpi[:]
            dp21.append((v1, w1))
            dp20.append((v0, w0))
            dp[2 * i + 1] = dp21
            dp[2 * i] = dp20
        elif 2 * i <= n:
            v0, w0 = LI()
            dp20 = dpi[:]
            dp20.appned((v0, w0))
            dp[2 * i] = dp20
        else:
            break
    M = 10 ** 5 + 1
    d = [[]]
    M0 = [0] * M
    for i in range(1, 1 << n.bit_length() // 2):
        d1 = defaultdict(int)
        d1[0] = 0
        di = M0[:]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                keyw = key + w
                valuev = value + v
                if keyw >= M: continue
                if d1[keyw] < valuev:
                    d1[keyw] = valuev
                    di[keyw] = valuev
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
        d.append(di)
    for _ in range(II()):
        V,L = LI()
        t = dp[V]
        lent = V.bit_length()
        n1 = lent // 2
        n2 = lent - n1
        vw2 = t[n1:]
        V = V >> n2
        d1 = defaultdict(int)
        d1[0] = 0
        dv = d[V]
        ans = dv[L]
        for v, w in vw2:
            for key, value in list(d1.items()):
                keyw = key + w
                if keyw > L: continue
                valuev = value + v
                if d1[keyw] < valuev:
                    d1[keyw] = valuev
                    if dv[L - keyw] + valuev > ans:
                        ans = dv[L - keyw] + valuev
        print(ans)
    return


solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict
import sys, itertools
input = sys.stdin.buffer.read
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LIR(n): return [LI() for _ in range(n)]

#solve
def solve():
    n = II()
    vw = LIR(n)
    nbit = 1 << n.bit_length()
    b = [i.bit_length() for i in range(nbit)]
    dp = [[None] * b[i] for i in range(nbit)]
    dp[1] = [(vw[0][0], vw[0][1])]
    for i in range(1 , nbit >> 1):
        dpi = dp[i]
        if 2 * i + 1 <= n:
            v1, w1 = vw[2 * i]
            v0, w0 = vw[2 * i - 1]
            dp21 = dp[2 * i + 1]
            dp20 = dp[2 * i]
            for i, j in enumerate(dpi):
                dp21[i] = j
                dp20[i] = j
            dp21[i + 1] = (v1, w1)
            dp20[i + 1] = (v0, w0)
        elif 2 * i <= n:
            v0, w0 = vw[2 * i - 1]
            dp20 = dp[2 * i]
            for i, j in enumerate(dpi):
                dp20[i] = j
            dp20[i + 1] = (v0, w0)
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << n.bit_length() // 2)]
    for i in range(1, 1 << n.bit_length() // 2):
        d1 = defaultdict(int)
        d1[0] = 0
        di = d[i]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                keyw = key + w
                valuev = value + v
                if keyw >= M: continue
                if d1[keyw] < valuev:
                    d1[keyw] = valuev
                    di[keyw] = valuev
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        lent = V.bit_length()
        n1 = lent // 2
        n2 = lent - n1
        vw2 = t[n1:]
        V = V >> n2
        d1 = defaultdict(int)
        d1[0] = 0
        dv = d[V]
        ans = dv[L]
        for v, w in vw2:
            for key, value in list(d1.items()):
                keyw = key + w
                if keyw > L: continue
                valuev = value + v
                if d1[keyw] < valuev:
                    d1[keyw] = valuev
                    if dv[L - keyw] + valuev > ans:
                        ans = dv[L - keyw] + valuev
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    b = [i.bit_length() for i in range(n + 1)]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = [None] * b[i]
        dpi = dp[i]
        for i, j in enumerate(t):
            if j <= n:
                v, w = vw[j - 1]
                dpi[i] = (v, w)
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        d1 = defaultdict(int)
        d1[0] = 0
        di = d[i]
        for v, w in dp[i]:
            for key, value in iter(d1.items()):
                if key + w >= M: continue
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        lent = len(t)
        n1 = lent // 2
        n2 = lent - n1
        vw2 = t[n1:]
        V = V >> n2
        d1 = defaultdict(int)
        d1[0] = 0
        for v, w in vw2:
            for key, value in iter(d1.items()):
                if key + w > L: continue
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
        ans = 0
        dv = d[V]
        for w, v in d1.items():
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        d1 = defaultdict(int)
        d1[0] = 0
        di = d[i]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                if key + w >= M: continue
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        d1 = defaultdict(int)
        d1[0] = 0
        for v, w in vw2:
            for key, value in list(d1.items()):
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        ans = 0
        dv = d[V]
        for w, v in d1.items():
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        d1 = defaultdict(int)
        d1[0] = 0
        di = d[i]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                if key + w > M: continue
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
    return
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        d1 = defaultdict(int)
        d1[0] = 0
        for v, w in vw2:
            for key, value in list(d1.items()):
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        ans = 0
        dv = d[V]
        for w, v in d1.items():
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        d1 = defaultdict(int)
        d1[0] = 0
        di = d[i]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j]
    return
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        d1 = defaultdict(int)
        d1[0] = 0
        for v, w in vw2:
            for key, value in list(d1.items()):
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        ans = 0
        dv = d[V]
        for w, v in d1.items():
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        d1 = defaultdict(int)
        d1[0] = 0
        di = d[i]
        for v, w in dp[i]:
            for key, value in list(d1.items()):
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        d1 = defaultdict(int)
        d1[0] = 0
        for v, w in vw2:
            for key, value in list(d1.items()):
                if d1[key + w] < value + v:
                    d1[key + w] = value + v
                    di[key + w] = value + v
        ans = 0
        dv = d[V]
        for w, v in d1.items():
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        di = d[i]
        for v, w in tmp:
            if di[w] < v:
                di[w] = v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        dv = d[V]
        for v, w in lis2:
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2 + 1)]
    for i in range(1, (1 << len(dp[n]) // 2 + 1)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        di = d[i]
        for v, w in tmp:
            if di[w] < v:
                di[w] = v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
    return  
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        dv = d[V]
        for v, w in lis2:
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << (n.bit_length() - 1)):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        for j in list(t):
            if j <= n:
                v, w = vw[j - 1]
                dp[i].append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2 + 1)]
    for i in range(1, (1 << len(dp[n]) // 2 + 1)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        di = d[i]
        for v, w in tmp:
            if di[w] < v:
                di[w] = v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        for v, w in lis2:
            if L - w < 0: continue
            if d[V][L - w] + v > ans:
                ans = d[V][L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << (n.bit_length() - 1)):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        for j in list(t):
            if j <= n:
                v, w = vw[j - 1]
                dp[i].append((v, w))
    d = defaultdict(list)
    M = 10 ** 5 + 1
    d[0] = [0] * M
    for i in range(1, (1 << len(dp[n]) // 2 + 1)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        d[i] = [0] * M
        for v, w in tmp:
            if d[i][w] < v:
                d[i][w] = v
        for j in range(M - 1):
            if d[i][j + 1] < d[i][j]:
                d[i][j + 1] = d[i][j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        for v, w in lis2:
            if L - w < 0: continue
            if d[V][L - w] + v > ans:
                ans = d[V][L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << (n.bit_length() - 1)):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        for j in list(t):
            if j <= n:
                v, w = vw[j - 1]
                dp[i].append((v, w))
    d = defaultdict(list)
    M = 10 ** 5 + 1
    for i in range(1, (1 << len(dp[n]) // 2 + 1)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        d[i] = [0] * M
        for v, w in tmp:
            if d[i][w] < v:
                d[i][w] = v
        for j in range(M - 1):
            if d[i][j + 1] < d[i][j]:
                d[i][j + 1] = d[i][j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        for _ in range(n2):
            V //= 2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        for v, w in lis2:
            if L - w < 0: continue
            if d[V][L - w] + v > ans:
                ans = d[V][L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    def f(l, v, w):
        tmp = []
        for vi, wi in l:
            tmp.append((vi, wi))
            tmp.append((vi + v, wi + w))
        tmp.sort(key=lambda x: x[1])
        res = []
        pre = -1
        for value, key in tmp:
            if value > pre:
                res.append((value, key))
                pre = value
        return res
    n = II()
    vw = LIR(n)
    dp = [[(0,0)] for i in range(1 << n.bit_length() + 1)]
    dp[1] = [(0, 0), (vw[0][0], vw[0][1])]
    for i in range(1, (1 << n.bit_length() - 1)):
        dp[2 * i] = f(dp[i], vw[2 * i - 1][0], vw[2 * i - 1][1])
        dp[2 * i + 1] = f(dp[i], vw[2 * i][0], vw[2 * i][1])
    for _ in range(II()):
        v, L = LI()
        t = dp[v]
        ok = -1
        ng = len(t)
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if t[mid][1] <= L:
                ok = mid
            else:
                ng = mid
        print(t[ok][0])

    return


#main
if __name__ == '__main__':
    solve()