Buggy python submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(V_MAX):
        val, w = map(int, input().split())
        i1 = i + 1
        i0 = (i + 1) >> 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)

    for i in range(V_MAX, n):
        val, w = map(int, input().split())

        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in reversed(range(w, L_MAX + 1)):
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():

    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 32 - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in reversed(range(w, L_MAX + 1)):
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():

    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 64 - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in reversed(range(w, L_MAX + 1)):
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 10
V_MAX = (1 << D_TH) - 64 - 1
dp = [[0] * (L_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i + 1) >> 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

# items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 10
V_MAX = (1 << D_TH) + 64 - 1
dp = [[0] * (L_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

# items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 378 - 1
dp = [[0] * (L_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

# items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 256 - 1
dp = [[0] * (L_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

# items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 256 - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 100 - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            if dp_[j] < dp[i0][j - w] + val:
                dp_[j] = dp[i0][j - w] + val
        dp.append(dp_)
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            if dp_[j] < dp[i0][j - w] + val:
                dp_[j] = dp[i0][j - w] + val
        dp.append(dp_)
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp.append(dp[i0][:])
        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            if dp[i1][j] < dp[i0][j - w] + val:
                dp[i1][j] = dp[i0][j - w] + val
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 10
V_MAX = (1 << D_TH) - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp.append(dp[i0][:])
        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 300 - 1
dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        for j in range(w):
            dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) - 1
dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        for j in range(w):
            dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)
        # print(w_sub)
        # print(v_sub)
        # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 50 - 1
dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        for j in range(L_MAX + 1):
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)
        # print(w_sub)
        # print(v_sub)
        # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

    print(ans)


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 9
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 9
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
        else:
            items.append((val, w))

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                vv.append(items[v - V_MAX][0])
                ww.append(items[v - V_MAX][1])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 9
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
        else:
            items.append((val, w))

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                vv.append(items[v - V_MAX][0])
                ww.append(items[v - V_MAX][1])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 8
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
        else:
            items.append((val, w))

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                vv.append(items[v - V_MAX][0])
                ww.append(items[v - V_MAX][1])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
        else:
            items.append((val, w))

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                vv.append(items[v - V_MAX][0])
                ww.append(items[v - V_MAX][1])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 9
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
        else:
            items.append((val, w))

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                vv.append(items[v - V_MAX][0])
                ww.append(items[v - V_MAX][1])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(items_sub)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) + 200 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
        else:
            items.append((val, w))

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                vv.append(items[v - V_MAX][0])
                ww.append(items[v - V_MAX][1])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(items_sub)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        items.append((val, w))
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                vv.append(items[v][0])
                ww.append(items[v][1])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(items_sub)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        items.append((val, w))
        if i < V_MAX:
            i1 = i + 1
            i0 = (i - 1) // 2 + 1
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = []
            while v >= V_MAX:
                items_sub.append(items[v])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(items_sub)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + items_sub[x][1]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + items_sub[x][0]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)
            # print(items_sub)
            # print(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        items.append((val, w))
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) // 2
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v >= V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                        if s_w > l:
                            break
                if s_w <= l:
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 9
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

    for i in range(n):
        val, w = map(int, input().split())
        items.append((val, w))
        if i < V_MAX:
            for j in range(L_MAX + 1):
                i1 = i + 1
                i0 = (i + 1) // 2
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v >= V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                        if s_w > l:
                            break
                if s_w <= l:
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    L_MAX = 10**5
    D_TH = 9
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX + 1):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v >= V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                        if s_w > l:
                            break
                if s_w <= l:
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    L_MAX = 10**5
    D_TH = 8
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX + 1):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v >= V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                if s_w <= l:
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    L_MAX = 10**5
    D_TH = 11
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX + 1):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v + 1 <= V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v > V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                if s_w <= l:
                    ans = max(ans, dp[V_MAX][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    L_MAX = 10**5
    D_TH = 9
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX + 1):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v + 1 <= V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v > V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                if s_w <= l:
                    ans = max(ans, dp[V_MAX][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    L_MAX = 10**5
    D_TH = 10
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX + 1):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v + 1 <= V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v > V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                if s_w <= l:
                    ans = max(ans, dp[V_MAX][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import sys


def main():
    input = sys.stdin.readline

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

    L_MAX = 10**5
    D_TH = 10
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v + 1 <= V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v > V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                if s_w <= l:
                    ans = max(ans, dp[l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1
        items_sub = [items[v]]
        while v > 0:
            v = (v - 1) // 2
            items_sub.append(items[v])

        m = len(items_sub)
        dp = [0] * (l + 1)
        for bit in range(1 << (m // 2)):
            s_val = s_w = 0
            for i, (val, w) in enumerate(items_sub[:m // 2]):
                if (bit >> i) & 1:
                    s_val += val
                    s_w += w
                    if s_w > l:
                        break
            if s_w <= l and dp[s_w] < s_val:
                dp[s_w] = s_val
        for i in range(l):
            if dp[i + 1] < dp[i]:
                dp[i + 1] = dp[i]

        ans = 0
        for bit in range(1 << (m - m // 2)):
            s_val = s_w = 0
            for i, (val, w) in enumerate(items_sub[m // 2:]):
                if (bit >> i) & 1:
                    s_val += val
                    s_w += w
                    if s_w > l:
                        break
            if s_w <= l:
                ans = max(ans, dp[l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1
        items_sub = [items[v]]
        while v > 0:
            v = (v - 1) // 2
            items_sub.append(items[v])

        m = len(items_sub)
        dp = [0] * (l + 1)
        for bit in range(1 << (m // 2)):
            s_val = s_w = 0
            for i, (val, w) in enumerate(items_sub[:m // 2]):
                if (bit >> i) & 1:
                    s_val += val
                    s_w += w
                    if s_w > l:
                        break
            if s_w <= l:
                dp[s_w] = max(dp[s_w], s_val)
        for i in range(l):
            dp[i + 1] = max(dp[i + 1], dp[i])

        ans = 0
        for bit in range(1 << (m - m // 2)):
            s_val = s_w = 0
            for i, (val, w) in enumerate(items_sub[m // 2:]):
                if (bit >> i) & 1:
                    s_val += val
                    s_w += w
                    if s_w > l:
                        break
            if s_w <= l:
                ans = max(ans, dp[l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict


def main():
    input = sys.stdin.readline

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

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1
        items_sub = [items[v]]
        while v > 0:
            v = (v - 1) // 2
            items_sub.append(items[v])

        m = len(items_sub)
        dp = [0] * (l + 1)
        for bit in range(1 << (m // 2)):
            s_val = s_w = 0
            for i, (val, w) in enumerate(items_sub[:m // 2]):
                if (bit >> i) & 1:
                    s_val += val
                    s_w += w
            if s_w <= l:
                dp[s_w] = max(dp[s_w], s_val)
        for i in range(l):
            dp[i + 1] = max(dp[i + 1], dp[i])

        ans = 0
        for bit in range(1 << (m - m // 2)):
            s_val = s_w = 0
            for i, (val, w) in enumerate(items_sub[m // 2:]):
                if (bit >> i) & 1:
                    s_val += val
                    s_w += w
            if s_w <= l:
                ans = max(ans, dp[l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict


def main():
    input = sys.stdin.readline

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

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1
        items_sub = [v]
        while v > 0:
            v = (v - 1) // 2
            items_sub.append(v)

        m = len(items_sub)
        dp = [0] * (l + 1)
        for bit in range(1 << (m // 2)):
            s_val = s_w = 0
            for i in range(m // 2):
                if (bit >> i) & 1:
                    s_val += items[items_sub[i]][0]
                    s_w += items[items_sub[i]][1]
            if s_w <= l:
                dp[s_w] = max(dp[s_w], s_val)
        for i in range(l):
            dp[i + 1] = max(dp[i + 1], dp[i])

        ans = 0
        for bit in range(1 << (m - m // 2)):
            s_val = s_w = 0
            for i in range(m - m // 2):
                if (bit >> i) & 1:
                    s_val += items[items_sub[m // 2 + i]][0]
                    s_w += items[items_sub[m // 2 + i]][1]
            if s_w <= l:
                ans = max(ans, dp[l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    d_th = 9
    queue = [(0, 0, [])]
    while queue:
        v, depth, items_sub = queue.pop()
        val, w = items[v]

        if depth < d_th:
            for j in range(MAX + 1):
                if j < w:
                    dp[depth + 1][j] = dp[depth][j]
                else:
                    dp[depth + 1][j] = max(dp[depth][j],
                                           dp[depth][j - w] + val)
        else:
            items_sub.append(v)

        if len(v_to_il[v]) > 0:
            if depth < d_th:
                for i, l in v_to_il[v]:
                    ans[i] = dp[depth + 1][l]
            else:
                cand = 0
                m = len(items_sub)
                for bit in range(1 << m):
                    s_val = s_w = 0
                    for i, v in enumerate(items_sub):
                        if (bit >> i) & 1:
                            s_val += items[v][0]
                            s_w += items[v][1]
                    for i, l in v_to_il[v]:
                        if s_w <= l:
                            ans[i] = max(ans[i], dp[d_th][l - s_w] + s_val)

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            queue.append((v * 2 + 1, depth + 1, items_sub))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1, items_sub))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    d_th = 11
    queue = [(0, 0, [])]
    while queue:
        v, depth, items_sub = queue.pop()
        val, w = items[v]

        if depth < d_th:
            for j in range(MAX + 1):
                if j < w:
                    dp[depth + 1][j] = dp[depth][j]
                else:
                    dp[depth + 1][j] = max(dp[depth][j],
                                           dp[depth][j - w] + val)
        else:
            items_sub.append(v)

        if len(v_to_il[v]) > 0:
            if depth < d_th:
                for i, l in v_to_il[v]:
                    ans[i] = dp[depth + 1][l]
            else:
                cand = 0
                m = len(items_sub)
                for bit in range(1 << m):
                    s_val = s_w = 0
                    for i, v in enumerate(items_sub):
                        if (bit >> i) & 1:
                            s_val += items[v][0]
                            s_w += items[v][1]
                    for i, l in v_to_il[v]:
                        if s_w <= l:
                            ans[i] = max(ans[i], dp[d_th][l - s_w] + s_val)

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            queue.append((v * 2 + 1, depth + 1, items_sub))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1, items_sub))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    queue = [(0, 0, [])]
    while queue:
        v, depth, items_sub = queue.pop()
        val, w = items[v]

        if depth < 10:
            for j in range(MAX + 1):
                if j < w:
                    dp[depth + 1][j] = dp[depth][j]
                else:
                    dp[depth + 1][j] = max(dp[depth][j],
                                           dp[depth][j - w] + val)
        else:
            items_sub.append(v)

        if len(v_to_il[v]) > 0:
            if depth < 10:
                for i, l in v_to_il[v]:
                    ans[i] = dp[depth + 1][l]
            else:
                cand = 0
                m = len(items_sub)
                for bit in range(1 << m):
                    s_val = s_w = 0
                    for i, v in enumerate(items_sub):
                        if (bit >> i) & 1:
                            s_val += items[v][0]
                            s_w += items[v][1]
                    for i, l in v_to_il[v]:
                        if s_w <= l:
                            ans[i] = max(ans[i], dp[10][l - s_w] + s_val)

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            queue.append((v * 2 + 1, depth + 1, items_sub))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1, items_sub))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    queue = [(0, 0, [])]
    while queue:
        v, depth, items_sub = queue.pop()
        val, w = items[v]

        if depth < 10:
            for j in range(MAX + 1):
                if j < w:
                    dp[depth + 1][j] = dp[depth][j]
                else:
                    dp[depth + 1][j] = max(dp[depth][j],
                                           dp[depth][j - w] + val)
        else:
            items_sub.append((val, w))

        if len(v_to_il[v]) > 0:
            if depth < 10:
                for i, l in v_to_il[v]:
                    ans[i] = dp[depth + 1][l]
            else:
                cand = 0
                m = len(items_sub)
                for bit in range(1 << m):
                    s_val = s_w = 0
                    for i, (val, w) in enumerate(items_sub):
                        if (bit >> i) & 1:
                            s_val += val
                            s_w += w
                    for i, l in v_to_il[v]:
                        if s_w <= l:
                            ans[i] = max(ans[i], dp[10][l - s_w] + s_val)

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            queue.append((v * 2 + 1, depth + 1, items_sub))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1, items_sub))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    queue = [(0, 0)]
    while queue:
        v, depth = queue.pop()
        val, w = items[v]

        for j in range(MAX + 1):
            if j < w:
                dp[depth + 1][j] = dp[depth][j]
            else:
                dp[depth + 1][j] = max(dp[depth][j], dp[depth][j - w] + val)

        if len(v_to_il[v]) > 0:
            for i, l in v_to_il[v]:
                ans[i] = dp[depth + 1][l]

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            queue.append((v * 2 + 1, depth + 1))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    input = sys.stdin.readline

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

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    def dfs(v, depth):
        val, w = items[v]
        for j in range(MAX + 1):
            if j < w:
                dp[depth + 1][j] = dp[depth][j]
            else:
                dp[depth + 1][j] = max(dp[depth][j], dp[depth][j - w] + val)

        if len(v_to_il[v]) > 0:
            for i, l in v_to_il[v]:
                ans[i] = dp[depth + 1][l]

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            dfs(v * 2 + 1, depth + 1)
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            dfs(v * 2 + 2, depth + 1)

    dfs(0, 0)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

q = int(input())
v_to_il = [[] for _ in range(n)]
flag = [False] * n
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    v_to_il[v].append((i, l))
    flag[v] = True
    while v > 0:
        v = (v - 1) // 2
        if flag[v]:
            break
        flag[v] = True

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(19)]
ans = [0] * q


def dfs(v, depth):
    val, w = items[v]
    for j in range(MAX + 1):
        if j < w:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j], dp[depth][j - w] + val)

    if len(v_to_il[v]) > 0:
        for i, l in v_to_il[v]:
            ans[i] = dp[depth + 1][l]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
flag = [False] * n
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    v_to_qi[v].append(i)
    v_to_l[v].append(l)
    flag[v] = True
    while v > 0:
        v = (v - 1) // 2
        flag[v] = True

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for i in range(len(v_to_qi[v])):
            ans[v_to_qi[v][i]] = dp[depth + 1][v_to_l[v][i]]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
flag = [False] * n
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    v_to_qi[v].append(i)
    v_to_l[v].append(l)
    flag[v] = True
    while v > 0:
        v = (v - 1) // 2
        flag[v] = True

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for i in range(len(v_to_qi[v])):
            ans[v_to_qi[v][i]] = dp[depth + 1][v_to_l[v][i]]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
flag = [False] * n
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    v_to_qi[v].append(i)
    v_to_l[v].append(l)
    flag[v] = True
    while v > 0:
        v = (v - 1) // 2
        flag[v] = True

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for i in range(len(v_to_qi[v])):
            ans[v_to_qi[v][i]] = dp[depth + 1][v_to_l[v][i]]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
qv_list = []
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    qv_list.append(v)
    v_to_qi[v].append(i)
    v_to_l[v].append(l)

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q

flag = [False] * n
for v in qv_list:
    flag[v] = True
    while v > 0:
        v = (v - 1) // 2
        flag[v] = True


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for qi, l in zip(v_to_qi[v], v_to_l[v]):
            ans[qi] = dp[depth + 1][l]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
qv_list = []
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    qv_list.append(v)
    v_to_qi[v].append(i)
    v_to_l[v].append(l)

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q

flag = [False] * n
for v in qv_list:
    flag[v] = True
    while v > 0:
        v //= 2
        flag[v] = True


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for qi, l in zip(v_to_qi[v], v_to_l[v]):
            ans[qi] = dp[depth + 1][l]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
qv_list = []
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    qv_list.append(v)
    v_to_qi[v].append(i)
    v_to_l[v].append(l)

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q

flag = [False] * n
for v in qv_list:
    flag[v] = True
    while v > 0:
        v //= 2
        flag[v] = True


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for qi, l in zip(v_to_qi[v], v_to_l[v]):
            ans[qi] = dp[depth + 1][l]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    v_to_qi[v].append(i)
    v_to_l[v].append(l)

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for qi, l in zip(v_to_qi[v], v_to_l[v]):
            ans[qi] = dp[depth + 1][l]

    if v * 2 + 1 < n:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    v_to_qi[v].append(i)
    v_to_l[v].append(l)

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for qi, l in zip(v_to_qi[v], v_to_l[v]):
            ans[qi] = dp[depth + 1][l]

    if v * 2 + 1 < n:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n:
        dfs(v * 2 + 2, depth + 1)


dfs(0, 0)
print(*ans, sep='\n')


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()