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

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        d = [None]*(maxL + 1)
        for j in range(maxL+1):
            if j < w:
                d[j] = dp[i>>1][j]
            else:
                d[j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
        dp.append(d)

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

if __name__ == "__main__":
    main()


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

if __name__ == "__main__":
    main()

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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

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

if __name__ == "__main__":
    main()

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

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

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

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()

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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

def main():
    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 11)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        while tmp > m:
            tmp >>= 1
            cnt += 1
        ret = 0
        for j in range(1 << cnt):
            weight_sum = 0
            value_sum = 0
            tmp = v
            idx = j
            while tmp > m:
                if idx & 1:
                    weight_sum += W[tmp - 1]
                    if weight_sum > L:
                        break
                    value_sum += V[tmp - 1]
                tmp >>= 1
                idx >>= 1
            else:
                value_sum += dp[tmp][L - weight_sum]
                ret = max(ret, value_sum)
        print(ret)
    return

if __name__ == "__main__":
    main()

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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

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

def main():
    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        while tmp > m:
            tmp >>= 1
            cnt += 1
        ret = 0
        for j in range(1 << cnt):
            weight_sum = 0
            value_sum = 0
            tmp = v
            idx = j
            while tmp > m:
                if idx & 1:
                    weight_sum += W[tmp - 1]
                    if weight_sum > L:
                        break
                    value_sum += V[tmp - 1]
                tmp >>= 1
                idx >>= 1
            else:
                value_sum += dp[tmp][L - weight_sum]
                ret = max(ret, value_sum)
        print(ret)
    return

if __name__ == "__main__":
    main()

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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(V[tmp-1])
        w_.append(W[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = dp[tmp][L]
    for j in range(1, 1 << cnt):
        weight_sum = 0
        value_sum = 0
        for v, w in zip(v_, w_):
            if j & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            j >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(v[tmp-1])
        w_.append(w[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = dp[tmp][L]
    for j in range(1, 1 << cnt):
        weight_sum = 0
        value_sum = 0
        for v, w in zip(v_, w_):
            if j & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            j >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(v[tmp-1])
        w_.append(w[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = 0
    for j in range(1 << cnt):
        weight_sum = 0
        value_sum = 0
        idx = j
        for v, w in zip(v_, w_):
            if idx & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(v[tmp-1])
        w_.append(w[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = 0
    for j in range(1 << cnt):
        weight_sum = 0
        value_sum = 0
        for v, w in zip(v_, w_):
            if j & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            j >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    while tmp > m:
        tmp >>= 1
        cnt += 1
    ret = 0
    for j in range(1 << cnt):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        while tmp > m:
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp >>= 1
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp >>= 1
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

m = min(n, 1 << 10)
dp = [[0]*(10**5 + 1) for _ in range(m + 1)]
for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(10**5+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)

q = I()
bl = m.bit_length()
for i in range(q):
    v, L = LI()
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - bl
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp >>= 1 
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>2][j]
        else:
            dp[i][j] = max(dp[i>>2][j], dp[i>>2][j - w] + v)

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp >>= 1
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i//2][j]
        else:
            dp[i][j] = max(dp[i//2][j], dp[i//2][j - w] + v)

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp //= 2
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    for j in range(maxL+1):
        if j < W[i-1]:
            dp[i][j] = dp[i//2][j]
        else:
            dp[i][j] = max(dp[i//2][j],dp[i//2][j-W[i-1]] + V[i-1])

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp //= 2
            idx >>= 1 
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    for j in range(maxL+1):
        if j < W[i-1]:
            dp[i][j] = dp[i//2][j]
        else:
            dp[i][j] = max(dp[i//2][j],dp[i//2][j-W[i-1]] + V[i-1])

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        for k in range(x):
            if j >> k & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp //= 2
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    for j in range(maxL+1):
        if j < W[i-1]:
            dp[i][j] = dp[i//2][j]
        else:
            dp[i][j] = max(dp[i//2][j],dp[i//2][j-W[i-1]] + V[i-1])

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        for k in range(x):
            if j >> k & 1:
                weight_sum += W[tmp - 1]
                value_sum += V[tmp - 1]
            tmp //= 2
        if weight_sum > L:
            continue
        value_sum += dp[tmp][L - weight_sum]
        ret = max(ret, value_sum)
    print(ret)


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

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

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

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

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
for _ in range(q):
    v, L = LI()
    m = int(math.log2(v)) + 1
    dp = [[0]*(L+1) for _ in range(m+1)]
    idx = v
    for i in range(m):
        for j in range(L+1):
            if j < W[idx-1]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j-W[idx-1]] + V[idx-1])
        idx //= 2
    print(dp[-1][L])

    

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

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

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

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

if __name__ == "__main__":
    main()