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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact

def make_combs(n, k):
    '''
        make [C(n, 0), C(n, 1), C(n, 2) ..... C(n, k)]
        n! / (n - k)! k!
    '''
    facts = make_facts(n)
    invs = [] # inverted for fraction
    for fact in facts:
        invs.append(pow(fact, MOD - 2, MOD))

    ret = []
    for i in range(0, n + 1):
        a = facts[n]
        #b = facts[i]
        #c = facts[n - i]
        ret.append(a * invs[i] * invs[n - i] % MOD)
    return ret


def _calc(n):
    ret = 2
    tmp = 1
    while tmp < n:
        print(tmp, ret)
        ret = (ret * ret) % MOD
        tmp *= 2
    if n - tmp > 0:
        t = _calc(n - tmp)
        ret *= t
    return ret

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x %= MOD
        n //= 2

    return K * x % MOD


def solve(n: int, a: int, b: int):
    #ret = ((2 ** n) - 1) % MOD
    #ret = (_calc(n) - 1) % MOD
    ret = (pow(2, n, MOD) - 1) % MOD
    #ret = (pow_k(2, n) - 1) % MOD
    combs = make_combs(n, n)
    ret = (ret + MOD * 2 - combs[a] - combs[b]) % MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()


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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_comb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a = a * (n - i) % MOD
        b = b * (i + 1) % MOD
    ret = get_fraction_mod(a, b)
    return ret


def solve(n: int, a: int, b: int):
    ret = (pow(2, n, MOD) - 1) % MOD
    ret = ret + MOD - make_comb(n, a)
    ret = ret + MOD - make_comb(n, b)
    ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    max_t = T + max(A)
    dp = [-1] * (max_t + 1)
    dp[0] = 0
    p = []
    for i in range(N):
        p.append((A[i], B[i]))
    p.sort()
    for i in range(N):
        for t in range(T - 1, -1, -1):
            if dp[t] >= 0:
                dp[t + p[i][0]] = max(dp[t + p[i][0]], dp[t] + p[i][1])
    ret = 0
    for v in dp:
        ret = max(ret, v)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()


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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    max_t = T + max(A)
    dp = [-1] * (max_t + 1)
    dp[0] = 0
    p = []
    for i in range(N):
        p.append((A[i], B[i]))
    p.sort()
    for i in range(N):
        for t in range(T - 1, -1, -1):
            if dp[t] >= 0:
                dp[t + p[i][0]] = max(dp[t + p[i][0]], dp[t] + p[i][1])
    ret = 0
    for v in dp:
        ret = max(ret, v)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(L: str):
    n = len(L)
    memo = [0] * (n + 1)
    memo[0] = 1
    for i in range(1, n + 1):
        memo[i] = memo[i - 1] * 3 % MOD

    ret = 0
    cnt = 0
    for i in range(n):
        c = L[i]
        if c == '1':
            rest = n - i - 1
            ret += memo[rest] * (2 ** cnt)
            cnt += 1
            #print(ret)
    ret = (ret + 2 ** cnt) % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = str(next(tokens))
    solve(L)

if __name__ == '__main__':
    main()


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

MOD = 1000000007  # type: int

def solve(L: str):
    n = len(L)
    memo = [0] * (n + 1)
    memo[0] = 1
    for i in range(1, n + 1):
        memo[i] = memo[i - 1] * 3 % MOD
    cum = [0] * (n + 1)
    cum[0] = 1
    for i in range(1, n + 1):
        cum[i] = (cum[i - 1] * 2) % MOD

    ret = 0
    cnt = 0
    for i in range(n):
        c = L[i]
        if c == '1':
            rest = n - i - 1
            ret = (ret + memo[rest] * cum[cnt]) % MOD
            cnt += 1
            #print(ret)
    ret = (ret + cum[cnt]) % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = str(next(tokens))
    solve(L)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
 
 
def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    def bsearch_l(val, D):
        l = -1
        r = Q - 1
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val > m:
                l = m
            else:
                r = m
        #print(val, l, r)
        return r
    def bsearch_r(val, D):
        l = 0
        r = Q
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val < D[m]:
                r = m
            else:
                l = m
        #print(val, l, r)
        return l
    a = []
    for i in range(N):
        a.append([X[i], max(0, -(X[i] - S[i]) - 1), max(0, -(X[i] - T[i]) - 1)])
    a.sort(key=lambda x: x[0])
    ret = [-1] * Q
    for tmp in a:
        l = bsearch_l(tmp[1], D)
        r = bsearch_r(tmp[2], D)
        #print(tmp)
        #print(l, r)
        for i in range(l, r + 1):
            if i >= 0 and i < Q and ret[i] < 0:
                ret[i] = tmp[0]
 
    for r in ret:
        print(r)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]" 
    T = [int()] * (N)  # type: "List[int]" 
    X = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(N, Q, S, T, X, D)
 
if __name__ == '__main__':
    main()

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


def solve(A: int, P: int):
    ret = (3 * A + P) // 2
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    solve(A, P)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 998244353  # type: int

def solve(N: int, a: "List[int]"):
    s = sum(a)
    dp = [[[0] * 2 for _ in range(s + 1)] for _ in range(N + 1)] # dp[idx][sum][]
    dp[0][0][0] = 1
    dp[0][0][1] = 1
    for i in range(N):
        for j in range(s + 1 - a[i]):
            dp[i + 1][j + a[i]][0] += dp[i][j][0]
            dp[i + 1][j + a[i]][1] += dp[i][j][1]
            dp[i + 1][j][0] += dp[i][j][0]
            dp[i + 1][j][1] += dp[i][j][1] * 2

    tmp = 0
    border = (s + 1) // 2
    uniq = 0
    #pprint(dp)
    for j in range(border, s + 1):
        tmp += dp[N][j][1]
        uniq += dp[N][j][0]
    #print(tmp, uniq)
    tmp -= uniq * 2
    tmp *= 3

    ret = (3 ** N) % MOD
    col_2 = (2 ** N) % MOD
    ret -= 3 + (col_2 - 2) * 3 + 3
    #print(ret)
    #for i in range(N):
    #    ret *= 3
    #    ret %= MOD
    #    col_2 *= 2
    #    col_2 %= MOD
    ret -= tmp
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()


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


def solve(N: int, S: str):
    white = []
    white.append(0)
    cur = 0
    for c in S:
        if c == '.':
            cur += 1
        white.append(cur)
    black = []
    black.append(0)
    cur = 0
    for c in S[::-1]:
        if c == '#':
            cur += 1
        black.append(cur)
    black.reverse()
    #print(white)
    #print(black)
    ret = float('inf')
    for i in range(N + 1):
        ret = min(ret, N - (white[i] + black[i]))
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def solve(S: str):
    n = len(S)
    while True:
        l = len(S)
        for i in range(len(S) - 1):
            if S[i] != S[i + 1]:
                S = S[:i] + S[i + 2:]
                break
        if l == len(S):
            break
    print(n - len(S))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


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


def solve(S: str):
    n = len(S)
    while True:
        l = len(S)
        i = 0
        while True:
            if i >= len(S) - 1:
                break
            if S[i] != S[i + 1]:
                S = S[:i] + S[i + 2:]
                i = max(i - 1, 0)
            else:
                i += 1
        if l == len(S):
            break
    print(n - len(S))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
 
 
def solve(n: int, m: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):
 
    def check_pos(target, a, x):
        ret = {}
        a_x = a + x
        a_x.sort()
        idx = 0
        while idx < len(a_x) and a_x[idx] < target[0]:
            dis = target[0] - a_x[idx]
            ret[a_x[idx]] = [dis, [target[0], dis]] # [pos, dis]
            idx += 1
        for i in range(len(target) - 1):
            while idx < len(a_x) and target[i] <= a_x[idx] <= target[i + 1]:
                pos = a_x[idx]
                l = a_x[idx] - target[i]
                r = target[i + 1] - a_x[idx]
                ret[pos] = [
                    min(l, r),
                    [target[i],     l],
                    [target[i + 1], r]
                ]
                idx += 1
        while idx < len(a_x):
            dis = a_x[idx] - target[-1]
            ret[a_x[idx]] = [dis, [target[-1], dis]] # [pos, dis]
            idx += 1
        return ret
 
    nearest_s = check_pos(s, t, x)
    nearest_t = check_pos(t, s, x)
    print('hoge')
    return
 
    for q in x:
        ret = min(
                min([(pos_dis[1] + nearest_t[pos_dis[0]][0]) for pos_dis in nearest_s[q][1:]]),
                min([(pos_dis[1] + nearest_s[pos_dis[0]][0]) for pos_dis in nearest_t[q][1:]]))
        print(ret)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [ int(next(tokens)) for _ in range(A) ]  # type: "List[int]"
    t = [ int(next(tokens)) for _ in range(B) ]  # type: "List[int]"
    x = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(A, B, Q, s, t, x)
 
if __name__ == '__main__':
    main()

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


def solve(S: str):
    s = int(S[:4] + S[5:7] + S[8:10])
    if s <= 20190430:
        ret = 'Heisei'
    else:
        ret = 'TBD'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys

def _solve(N: int, K: int, A: "List[int]"):
    ret = sum(A)
    digits = 0
    while K >= 2 ** digits:
        digits += 1
    counts = [0] * digits
    for num in A:
        n = num
        idx = 0
        while n > 0 and idx < digits:
            if n % 2 == 1:
                counts[idx] += 1
            idx += 1
            n //= 2
    tmp = 0
    for idx, c in enumerate(counts):
        if N - 2 * c > 0 and tmp + 2 ** idx <= K:
            ret += (2 ** idx) * (N - 2 * c)
            tmp += 2 ** idx

    if digits > 0:
        last = counts[-1]
        if N - 2 * last > 0:
            most_bit = 2 ** (digits - 1)
            K_ = K - most_bit
            ret = max(ret, _solve(N, K_, A) + most_bit * (N - 2 * last))
    #print(N, K, A)
    #print(ret)
    #print('--------------- ')
    return ret

def solve(N: int, K: int, A: "List[int]"):
    ret = _solve(N, K, A)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


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

def _solve(counts, k, n, used=[]):
    ret = 0
    digits = 0
    while k >= 2 ** digits:
        digits += 1
    tmp = 0
    for idx, c in enumerate(counts):
        if not idx in used:
            if n - 2 * c > 0 and tmp + 2 ** idx <= k:
                ret += (2 ** idx) * (n - c)
                tmp += 2 ** idx
            else:
                ret += (2 ** idx) * c
    #print('k : %d, digits : %d, ret : %d, used : %s' % (k, digits, ret, used))
    #print('counts : %s' % (counts))
    if digits > 0:
        last = counts[digits - 1]
        if n - 2 * last >= 0:
            most_bit = 2 ** (digits - 1)
            k_ = k - most_bit
            #ret = max(ret, _solve(counts[:digits - 1], k_, n) + most_bit * (n - last))
            ret = max(ret, _solve(counts, k_, n, used + [digits - 1]) + most_bit * (n - last))
        #most_bit = 2 ** (digits - 1)
        #k_ = k - most_bit
        #ret = max(ret, _solve(counts, k_, n, used + [digits - 1]) + most_bit * (n - last))
    #print(ret)
    return ret


def solve(N: int, K: int, A: "List[int]"):
    counts = [0] * 45
    for num in A:
        n = num
        idx = 0
        while n > 0:
            if n % 2 == 1:
                counts[idx] += 1
            idx += 1
            n //= 2
    ret = _solve(counts, K, N)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    par = [[] for _ in range(N)]
    chi = [[] for _ in range(N)]
    root = None
    for i in range(N + M - 1):
        chi[A[i] - 1].append(B[i] - 1)
        par[B[i] - 1].append(A[i] - 1)

    #print(chi)
    #print(par)
    for i in range(N):
        if len(par[i]) < 1:
            root = i
            par[i].append(-1)
            break

    depths = [0] * (N)
    def dfs(i, d):
        depths[i] = max(depths[i], d)
        for ch in chi[i]:
            dfs(ch, d + 1)
    dfs(root, 0)
    #print(depths)

    for i in range(N):
        if len(par[i]) > 1:
            for p in par[i]:
                if depths[p] == depths[i] - 1:
                    ret = p
        else:
            ret = par[i][0]
        print(ret + 1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N-1+M)  # type: "List[int]" 
    B = [int()] * (N-1+M)  # type: "List[int]" 
    for i in range(N-1+M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


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


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    par = [[] for _ in range(N)]
    chi = [[] for _ in range(N)]
    root = None
    for i in range(N + M - 1):
        chi[A[i] - 1].append(B[i] - 1)
        par[B[i] - 1].append(A[i] - 1)

    #print(chi)
    #print(par)
    for i in range(N):
        if len(par[i]) < 1:
            root = i
            par[i].append(-1)
            break

    cur = {root}
    while len(cur) > 0:
        #print(cur)
        nex = set()
        for idx in cur:
            for c in chi[idx]:
                if len(par[c]) < 2:
                    nex.add(c)
                else:
                    par[c].remove(idx)
        cur = nex

    for i in range(N):
        ret = par[i][0]
        print(ret + 1)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N-1+M)  # type: "List[int]" 
    B = [int()] * (N-1+M)  # type: "List[int]" 
    for i in range(N-1+M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, h: "List[int]"):
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N):
        for j in range(K):
            if i + j + 1 < N:
                dp[i + j + 1] = min(dp[i + j + 1], dp[i] + abs(h[i + j + 1] - h[i]))
    print(dp[N - 1])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, h)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)
 
 
def solve(N: int, K: int, h: "List[int]"):
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N):
        for j in range(K):
            if i + j + 1 < N:
                dp[i + j + 1] = min(dp[i + j + 1], dp[i] + abs(h[i + j + 1] - h[i]))
    print(dp[N - 1])
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, h)
 
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, -1, -1):
            if j + w[i] <= W:
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i])
    ret = max(dp)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, -1, -1):
            if j + w[i] <= W:
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i])
    ret = max(dp)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()