Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, L = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, readline().split())
        if c > L:
            continue
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    Q, *ST = map(int, read().split())

    dist = [[(INF, INF)] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = (0, 0)
        hq = [(0, 0, i)]
        while hq:
            refuel, used, v = heappop(hq)
            if dist[i][v] < (refuel, used):
                continue
            for nv, cost in G[v]:
                if used + cost <= L:
                    if dist[i][nv] > (refuel, used + cost):
                        dist[i][nv] = (refuel, used + cost)
                        heappush(hq, (refuel, used + cost, nv))
                else:
                    if dist[i][nv] > (refuel + 1, cost):
                        dist[i][nv] = (refuel + 1, cost)
                        heappush(hq, (refuel + 1, cost, nv))

    ans = [0] * Q
    for i, (s, t) in enumerate(zip(*[iter(ST)] * 2)):
        ans[i] = dist[s - 1][t - 1][0] if dist[s - 1][t - 1][0] != INF else -1

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


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, L = map(int, readline().split())
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, readline().split())
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

    Q, *ST = map(int, read().split())

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    H = [[INF] * N for _ in range(N)]
    for i in range(N - 1):
        for j in range(i + 1, N):
            if G[i][j] <= L:
                H[i][j] = H[j][i] = 1

    for i in range(N):
        H[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if H[i][j] > H[i][k] + H[k][j]:
                    H[i][j] = H[i][k] + H[k][j]

    ans = [0] * Q
    for i, (s, t) in enumerate(zip(*[iter(ST)] * 2)):
        s -= 1
        t -= 1
        if H[s][t] == INF:
            ans[i] = -1
        else:
            ans[i] = H[s][t] - 1

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


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    dp = [0] * (N + 1)
    ans = 0

    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N):
            if S[i] == S[j]:
                dp[j] = dp[j + 1] + 1
                if ans < min(dp[j], j - i):
                    ans = min(dp[j], j - i)
            else:
                dp[j] = 0

    print(ans)
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    ans = 0
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(N - 1, i - 1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            if ans < min(j - i, dp[i][j]):
                ans = min(j - i, dp[i][j])

    print(ans)
    return


if __name__ == '__main__':
    main()

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(N - 1, -1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1

    ans = 0
    for i in range(N):
        for j in range(N):
            if ans < min(dp[i][j], j - i):
                ans = min(dp[i][j], j - i)

    print(ans)
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    ans = 0
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(N - 1, i - 1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            if ans < min(j - i, dp[i][j]):
                ans = min(j - i, dp[i][j])

    print(ans)
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *H = map(int, read().split())
    
    ans = []
    c = 0
    for i in range(N-1):
        if H[i] >= H[i+1]:
            c += 1
        else:
            ans.append(c)
            c = 0
            
    if c > 0:
        ans.append(c)
            
    print(max(ans))
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *H = map(int, read().split())

    ans = []
    c = 0
    for i in range(N - 1):
        if H[i] >= H[i + 1]:
            c += 1
        else:
            ans.append(c)
            c = 0

    ans.append(c)

    print(max(ans))
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)

    A = list(range(N))
    for _ in range(10):
        for i, a in enumerate(A):
            if S[a] == 'L':
                A[i] -= 1
            else:
                A[i] += 1

    B = A
    for _ in range(99):
        A, B = B, list(range(N))
        for _ in range(10):
            for i, b in enumerate(B):
                B[i] = A[b]

    ans = [0] * N
    for b in B:
        ans[b] += 1

    print(*ans)
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)

    A = list(range(N))
    for _ in range(10):
        for i, a in enumerate(A):
            if S[a] == 'L':
                A[i] -= 1
            else:
                A[i] += 1

    B = A
    for _ in range(99):
        A, B = B, list(range(N))
        for _ in range(10):
            for i, b in enumerate(B):
                B[i] = A[b]

    ans = [0] * N
    for b in B:
        ans[b] += 1

    print(*ans)
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    S = S[::-1]

    dp = [0] * 13
    dp[0] = 1
    p = 1

    for c in S:
        dp, dp_prev = [0] * 13, dp
        for k in range(13):
            if c == '?':
                for j in range(10):
                    dp[(p * j + k) % 13] = (dp[(p * j + k) % 13] + dp_prev[k]) % MOD
            else:
                dp[(p * int(c) + k) % 13] = (dp[(p * int(c) + k) % 13] + dp_prev[k]) % MOD

        p = p * 10 % 13

    print(dp[5])
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)
    power = [0] * N
    power[0] = 1
    for i in range(N - 1):
        power[i + 1] = 10 * power[i] % 13

    S = S[::-1]

    Q = [i for i, c in enumerate(S) if c == '?']
    M = len(Q)

    const = 0
    for i, c in enumerate(S):
        if c != '?':
            const = (const + power[i] * int(c)) % 13

    dp = [0] * 13
    dp[const] = 1

    for i in range(M):
        dp, dp_prev = [0] * 13, dp
        p = power[Q[i]]
        for j in range(10):
            for k in range(13):
                idx = (p * j + k) % 13
                dp[idx] = (dp[idx] + dp_prev[k]) % MOD

    print(dp[5])
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
from bisect import bisect_left

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = tuple(int(input()) for _ in range(N))
    B = [A[0]]

    for a in A[1:]:
        if a <= B[0]:
            B.insert(0, a)
        else:
            B[bisect_left(B, a) - 1] = a

    print(len(B))


if __name__ == '__main__':
    main()


Fixed submission:
from sys import stdin, setrecursionlimit
from bisect import bisect_left
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = tuple(int(input()) for _ in range(N))
    B =deque([A[0]])

    for a in A[1:]:
        if a <= B[0]:
            B.appendleft(a)
        else:
            B[bisect_left(B, a) - 1] = a

    print(len(B))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    L, R = map(int, readline().split())

    if L - R + 1 >= 2019:
        print(0)
    else:
        A = [i % 2019 for i in range(L, R + 1)]
        A.sort()
        print(A[0] * A[1])

    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def distance2_nd(p, q):
    return sum((px - qx) ** 2 for px, qx in zip(p, q))


def isqrt(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1) // 2
        y = (x + n // x) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x
    elif n == 0:
        return 0
    else:
        raise ValueError("isqrt() argument must be nonnegative")


def main():
    N, D = map(int, readline().split())
    X = [list(map(int, readline().split())) for _ in range(N)]

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            d2 = distance2_nd(X[i], X[j])
            di = isqrt(d2)
            if di * di == d2:
                ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
import numpy as np

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())
    A = np.array(A)
    C = np.zeros((N, N))
    for i in range(N):
        C[i, i] = C[i, (i + 1) % N] = 1

    X = np.linalg.solve(C, A)
    X = [int(x * 2) for x in X]

    print(*X)
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())
    X = [0] * N
    X[-1] = A[-1]
    for i, a in enumerate(A[:-1]):
        if i % 2:
            X[-1] += a
        else:
            X[-1] -= a

    for i in range(N - 2, -1, -1):
        X[i] = 2 * A[i] - X[i + 1]

    print(*X)
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    S = list(map(int, readline().split()))
    T = list(map(int, readline().split()))

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j]) % MOD
            if S[i] == T[j]:
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD

    print(dp[N][M])
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    S = list(map(int, readline().split()))
    T = list(map(int, readline().split()))

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j]) % MOD
            if S[i] == T[j]:
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD

    print(dp[N][M])
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, K = map(int, readline().split())

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    def solve(n, m, k):
        ans = 0
        for j in range(1, k):
            tmp = 0
            for i in range(1, n):
                tmp = (tmp + com(m * i, j) * com(m * (n - i), k - j)) % MOD
            ans = (ans + tmp * j * (k - j)) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, K = map(int, readline().split())

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    def solve(n, m, k):
        ans = 0
        for d in range(1, n):
            ans = (ans + com(n * m - 2, k - 2) * (m ** 2) * (n - d) * d) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
from math import log2, ceil

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K = map(int, readline().split())

    ans = 0
    for n in range(1, N + 1):
        if n >= K:
            ans += 1
        else:
            ans += pow(2, -ceil(log2(K / n)))

    print(ans / N)
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys
from math import log2, ceil

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K = map(int, readline().split())

    ans = 0
    for n in range(1, N + 1):
        if n >= K:
            ans += 1
        else:
            ans += pow(2, -ceil(log2(K / n)))

    print(ans / N)
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    A, B, C, D, E = map(int, readline().split())

    if E - A > K:
        print(':(')
    else:
        print('Yay!')

    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    (*A,) = map(int, read().split())
    k = A[-1]

    for i in range(5):
        for j in range(i + 1, 5):
            if A[j] - A[i] > k:
                print(':(')
                return

    print('Yay!')
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    X, Y, Z, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    AB = []
    for a in A:
        for b in B:
            AB.append(a + b)

    AB.sort(reverse=True)
    AB = AB[:K]

    ABC = []
    for ab in AB:
        for c in C:
            ABC.append(ab + c)

    ABC.sort(reverse=True)

    print('\n'.join(map(str, ABC[:K])))

    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    X, Y, Z, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    AB = []
    for a in A:
        for b in B:
            AB.append(a + b)

    AB.sort(reverse=True)
    AB = AB[:K]

    ABC = []
    for ab in AB:
        for c in C:
            ABC.append(ab + c)

    ABC.sort(reverse=True)

    print('\n'.join(map(str, ABC[:K])))

    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


N = int(readline())
B = list(map(int, readline().split()))

def main():
    def dfs(vec):
        i = 0
        zero_only = True
        for j in range(len(vec)):
            if vec[j] > 0:
                zero_only = False
                i += 1
                if vec[j] == i:
                    vec[j] = 0
                    ret = dfs(vec)
                    vec[j] = i
                    if ret != False:
                        ret.append(i)
                        return ret
        if zero_only:
            return []
        else:
            return False

    ans = dfs(B)
    if ans == False:
        print(-1)
    else:
        print(*ans, sep='\n')

if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


N = int(readline())
B = list(map(int, readline().split()))


def main():
    ans = []
    while B:
        found = False
        for i in range(len(B), 0, -1):
            if i == B[i - 1]:
                ans.append(i)
                del B[i - 1]
                found = True
                break
        if not found:
            print(-1)
            return
    print(*reversed(ans), sep='\n')


if __name__ == '__main__':
    main()

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


N = int(readline())
B = list(map(int, readline().split()))


def dfs(vec):
    i = 0
    zero_only = True
    for j in range(len(vec)):
        if vec[j] > 0:
            zero_only = False
            i += 1
            if vec[j] == i:
                vec[j] = 0
                ret = dfs(vec)
                vec[j] = i
                if ret != False:
                    ret.append(i)
                    return ret
    if zero_only:
        return []
    else:
        return False


ans = dfs(B)
if ans == False:
    print(-1)
else:
    print(*ans, sep='\n')


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


N = int(readline())
B = list(map(int, readline().split()))


def main():
    ans = []
    while B:
        found = False
        for i in range(len(B), 0, -1):
            if i == B[i - 1]:
                ans.append(i)
                del B[i - 1]
                found = True
                break
        if not found:
            print(-1)
            return
    print(*reversed(ans), sep='\n')


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for sum_w in range(W + 1):
            if sum_w - weight[i] >= 0:
                dp[i + 1][sum_w] = dp[i][sum_w - weight[i]] + value[i]
            if dp[i + 1][sum_w] < dp[i][sum_w]:
                dp[i + 1][sum_w] = dp[i][sum_w]

    print(dp[N][W])
    return


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for sum_w in range(W + 1):
            if sum_w - weight[i] >= 0:
                dp[i + 1][sum_w] = dp[i][sum_w - weight[i]] + value[i]
            if dp[i + 1][sum_w] < dp[i][sum_w]:
                dp[i + 1][sum_w] = dp[i][sum_w]

    print(dp[N][W])
    return


if __name__ == '__main__':
    main()