Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dict = defaultdict(int)
for a in A:
    dict[a] += 1

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if dict[1] == 0 else dp[1] = 0
for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])

Fixed submission:
from collections import defaultdict
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dict = defaultdict(int)
for a in A:
    dict[a] += 1

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
S = [str(input()) for i in range(H)]

L = [[0 for j in range(W)] for i in range(H)]
R = [[0 for j in range(W)] for i in range(H)]
U = [[0 for j in range(W)] for i in range(H)]
D = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        L[i][j] = 0 if S[i][j] == '#' else 1 + (0 if j == 0 else L[i][j-1])
    for j in range(W-1, -1, -1):
        R[i][j] = 0 if S[i][j] == '#' else 1 + (0 if j == W-1 else R[i][j+1])
for j in range(W):
    for i in range(H):
        U[i][j] = 0 if S[i][j] == '#' else 1 + (0 if i == 0 else U[i-1][j])
    for i in range(H-1, -1, -1):
        D[i][j] = 0 if S[i][j] == '#' else 1 + (0 if i == H-1 else D[i+1][j])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)

Fixed submission:
H, W = map(int, input().split())
S = [str(input()) for i in range(H)]

L = [[0 for j in range(W)] for i in range(H)]
R = [[0 for j in range(W)] for i in range(H)]
U = [[0 for j in range(W)] for i in range(H)]
D = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        L[i][j] = 0 if S[i][j] == '#' else 1 + (0 if j == 0 else L[i][j-1])
    for j in range(W-1, -1, -1):
        R[i][j] = 0 if S[i][j] == '#' else 1 + (0 if j == W-1 else R[i][j+1])
for j in range(W):
    for i in range(H):
        U[i][j] = 0 if S[i][j] == '#' else 1 + (0 if i == 0 else U[i-1][j])
    for i in range(H-1, -1, -1):
        D[i][j] = 0 if S[i][j] == '#' else 1 + (0 if i == H-1 else D[i+1][j])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)
Buggy python submission (verdict: Runtime Error):
N, A, B, C = map(int, input().split())

mod = 10 ** 9 + 7
table = [1] * (2 * N + 1)
for i in range(2*N):
    table[i+1] = table[i] * (i+1) % mod


def invmod(a, mod):
    # mod が素数の時に成立する
    return pow(a, mod - 2, mod)


def cmb(n, r):
    return (table[n] * invmod(table[r]) * invmod(table[n - r])) % mod


def solve(a, b):
    res = 0
    for i in range(N):
        res += ((i + N) * cmbs[i] * pow(b, i, mod)) % mod
        res %= mod
    return (pow(a, N, mod) * res) % mod


a = A * invmod(A + B)
b = B * invmod(A + B)
c = C * invmod(100)
cmbs = [cmb(i + N - 1, i) for i in range(N)]

Ea = solve(a, b)
Eb = solve(b, a)
ans = ((Ea + Eb) * invmod(1 - c)) % mod
print(ans)

Fixed submission:
N, A, B, C = map(int, input().split())

mod = 10 ** 9 + 7
table = [1] * (2 * N + 1)
for i in range(2*N):
    table[i+1] = table[i] * (i+1) % mod


def invmod(a, mod=mod):
    # mod が素数の時に成立する
    return pow(a, mod - 2, mod)


def cmb(n, r):
    return (table[n] * invmod(table[r]) * invmod(table[n - r])) % mod


def solve(a, b):
    res = 0
    for i in range(N):
        res += ((i + N) * cmbs[i] * pow(b, i, mod)) % mod
        res %= mod
    return (pow(a, N, mod) * res) % mod


a = A * invmod(A + B, mod)
b = B * invmod(A + B, mod)
c = C * invmod(100, mod)
cmbs = [cmb(i + N - 1, i) for i in range(N)]

Ea = solve(a, b)
Eb = solve(b, a)
ans = ((Ea + Eb) * invmod(1 - c, mod)) % mod
print(ans)
Buggy python submission (verdict: Runtime Error):
Q = int(input())

mod = 10 ** 6 + 3
table = [1]
for i in range(1, mod):
    table.append(table[-1]*i % mod)

for i in range(Q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
    else:
        y = x * pow(d, mod - 2, mod)% mod
        print(pow(d, n, mod) * table[y + n - 1] * pow(table[y - 1], mod - 2, mod) % mod)

Fixed submission:
Q = int(input())

mod = 10 ** 6 + 3
table = [1]
for i in range(1, mod):
    table.append(table[-1]*i % mod)

for i in range(Q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
    else:
        y = x * pow(d, mod - 2, mod) % mod
        if y + n - 1 >= mod:
            print(0)
        else:
            print(pow(d, n, mod) * table[y + n - 1] * pow(table[y - 1], mod - 2, mod) % mod)

Buggy python submission (verdict: Runtime Error):
Q = int(input())

mod = 10 ** 6 + 3
table = [1]
for i in range(1, mod):
    table.append(table[-1]*i % mod)

for i in range(Q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
    else:
        print(pow(d, n, mod) * table[y + n - 1] * pow(table[y - 1], mod - 2, mod) % mod)

Fixed submission:
Q = int(input())

mod = 10 ** 6 + 3
table = [1]
for i in range(1, mod):
    table.append(table[-1]*i % mod)

for i in range(Q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
    else:
        y = x * pow(d, mod - 2, mod) % mod
        if y + n - 1 >= mod:
            print(0)
        else:
            print(pow(d, n, mod) * table[y + n - 1] * pow(table[y - 1], mod - 2, mod) % mod)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
V = list(map(int, input().split()))

if K <= 2:
    print(max(V[0], V[1], 0))
    quit()


ans = 0
for a in range(min(N, K)+1):
    for b in range(min(N-a, K-a)+1):
        V_ = sorted(V[:a] + V[-b:]) if b >= 1 else sorted(V[:a])
        tmp = K - (a+b)
        curMinus = 0
        for v in V_:
            if v < 0 and tmp > 0:
                tmp -= 1
                curMinus += -v
        ans = max(ans, sum(V_)+curMinus)

print(ans)

Fixed submission:
N, K = map(int, input().split())
V = list(map(int, input().split()))

if K <= 2:
    print(max(V[0], V[-1], 0))
    quit()


ans = 0
for a in range(min(N, K)+1):
    for b in range(min(N-a, K-a)+1):
        V_ = sorted(V[:a] + V[-b:]) if b >= 1 else sorted(V[:a])
        tmp = K - (a+b)
        curMinus = 0
        for v in V_:
            if v < 0 and tmp > 0:
                tmp -= 1
                curMinus += -v
        ans = max(ans, sum(V_)+curMinus)

print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

if N == 1:
    print(max(A[0], BC[0][1]))
    quit()

heapq.heapify(A)
for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        curPopped = 0
        while curPopped < b:
            a = heapq.heappop(A)
            if a >= c:
                heapq.heappush(A, a)
                break
            curPopped += 1
        for i in range(curPopped):
            heapq.heappush(A, c)

print(sum(A))

Fixed submission:
N, M, K = map(int, input().split())

mod = 10**9 + 7
table = [1]
for i in range(N*M):
    table.append(table[-1] * (i+1) % mod)


def inv(N):
    return pow(N, mod-2, mod)  # Why mod?


def cmb(n, r):
    return table[n] * inv(table[n-r]*table[r]) % mod


print((M ** 2 * (N ** 3 - N) + N ** 2 * (M ** 3 - M)) // 6 * cmb(M * N - 2, K - 2) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = str(input())
ans = 0

for j in range(1, N+1):
    if S[-j] == '#':
        j += 1
    else:
        break

if j == 1:
    last = 0
else:
    last = j-1
i = 0
while i < N:
    if S[i:i+2] == '#.':
        ans += 1
        new_S = S[:i+1] + '#' + S[i+2:]
        S = new_S
    i += 1

print(min(ans, N-ans-last))

Fixed submission:
N = int(input())
S = str(input())

ans = [S.count('.')]
for i in range(N):
    temp = ans[-1]
    if S[i] == '#':
        temp += 1
    else:
        temp -= 1
    ans.append(temp)
    
print(min(ans))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = str(input())
ans = 0

for j in range(1, N+1):
    if S[-j] == '#':
        j += 1
    else:
        break

if j == 1:
    last = 0
else:
    last = j-1
i = 0
while i < N:
    if S[i:i+2] == '#.':
        ans += 1
        S = S[:i+1] + '#' + S[i+2:]
    i += 1

print(min(ans, N-ans-last))


Fixed submission:
N = int(input())
S = str(input())

ans = [S.count('.')]
for i in range(N):
    temp = ans[-1]
    if S[i] == '#':
        temp += 1
    else:
        temp -= 1
    ans.append(temp)
    
print(min(ans))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = str(input())
ans = 0

for j in range(1, N+1):
    if S[-j] == '#':
        j += 1
    else:
        break

if j == 1:
    last = 0
else:
    last = j-1
i = 0
while i < N:
    if S[i:i+2] == '#.':
        ans += 1
        S = S[:i+1] + '#' + S[i+2:]
    i += 1

print(min(ans, N-ans-last))

Fixed submission:
N = int(input())
S = str(input())

ans = [S.count('.')]
for i in range(N):
    temp = ans[-1]
    if S[i] == '#':
        temp += 1
    else:
        temp -= 1
    ans.append(temp)
    
print(min(ans))
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sumsofAandB = sorted([a+b for a in A for b in B])
sumsofAll = sorted([ab+c for ab in sumsofAandB for c in C], reverse=True)
for i in range(K):
    print(sumsofAll[i])

Fixed submission:
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sumsofAandB = sorted([a+b for a in A for b in B], reverse=True)[:K]
sumsofAll = sorted([ab+c for ab in sumsofAandB for c in C], reverse=True)
for i in range(K):
    print(sumsofAll[i])
Buggy python submission (verdict: Time Limit Exceeded):
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
dp[1] = [i % S[0] for i in range(X+1)]
S = [None] + S

for i in range(2, N+1):
    for j in range(X+1):
        dp[i][j] = (dp[i-1][j]*(i-1) + dp[i-1][j%S[i]]) % mod


print(dp[-1][-1])

Fixed submission:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
dp[1] = [i % S[0] for i in range(X+1)]
S = [None] + S

for i in range(2, N+1):
    for j in range(X+1):
        dp[i][j] = (dp[i-1][j]*(i-1) + dp[i-1][j%S[i]]) % mod


print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
dp[1] = [i % S[0] for i in range(X+1)]
S = [None] + S

for i in range(2, N+1):
    for j in range(X+1):
        dp[i][j] = (dp[i-1][j]*(i-1) + dp[i-1][j%S[i]]) % mod


print(dp[-1][-1])

Fixed submission:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
dp[1] = [i % S[0] for i in range(X+1)]
S = [None] + S

for i in range(2, N+1):
    for j in range(X+1):
        dp[i][j] = (dp[i-1][j]*(i-1) + dp[i-1][j%S[i]]) % mod


print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for i in range(A)]
S = [-(10**11+1)] + S + [10**11+1]
T = [int(input()) for i in range(B)]
T = [-(10**11+1)] + T + [10**11+1]
X = [int(input()) for i in range(Q)]

for x in X:
    s_left = bisect.bisect_right(S, x)
    s_right = s_left - 1
    t_left = bisect.bisect_right(T, x)
    t_right = t_left - 1
    s1, s2 = S[s_left], S[s_right]
    t1, t2 = T[t_left], T[t_right]
    dis1 = abs(s1-x)+abs(s1-t1)
    dis2 = abs(s1-x)+abs(s1-t2)
    dis3 = abs(s2-x)+abs(s2-t1)
    dis4 = abs(s2-x)+abs(s2-t2)
    dis5 = abs(t1 - x) + abs(t1 - s1)
    dis6 = abs(t1 - x) + abs(t1 - s2)
    dis7 = abs(t2 - x) + abs(t2 - s1)
    dis8 = abs(t2 - x) + abs(t2 - s2)
    print(min(dis1, dis2, dis3, dis4, dis5, dis6, dis7, dis8))

Fixed submission:
A, B, Q = map(int, input().split())
inf = 10 ** 11
S = [-inf] + [int(input()) for i in range(A)] + [inf]
T = [-inf] + [int(input()) for i in range(B)] + [inf]
X = [int(input()) for i in range(Q)]
import bisect

for q in range(Q):
    x = X[q]
    s1 = bisect.bisect_right(S, x)
    s2 = s1 - 1
    t1 = bisect.bisect_right(T, x)
    t2 = t1 - 1
    s1, s2 = S[s1], S[s2]
    t1, t2 = T[t1], T[t2]
    dis1 = abs(x - s1) + abs(s1 - t1)
    dis2 = abs(x - s2) + abs(s2 - t2)
    dis3 = abs(x - t1) + abs(t1 - s1)
    dis4 = abs(x - t2) + abs(t2 - s2)
    dis5 = abs(x - s1) + abs(s1 - t2)
    dis6 = abs(x - s2) + abs(s2 - t1)
    dis7 = abs(x - t1) + abs(t1 - s2)
    dis8 = abs(x - t2) + abs(t2 - s1)
    dis = min(dis1, dis2, dis3, dis4, dis5, dis6, dis7, dis8)
    print(dis)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

# A内の整数値を用いて作られる最小の整数を求めよ、という問題


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


ans = gcd(A[0], A[1])
for i in range(1, N):
    ans = min(ans, gcd(A[i], A[j]))


print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

# A内の整数値を用いて作られる最小の整数を求めよ、という問題


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


ans = gcd(A[0], A[1])
for i in range(1, N):
    ans = min(ans, gcd(ans, A[i]))


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

# A内の整数値を用いて作られる最小の整数を求めよ、という問題


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


ans = float('inf')
for i in range(N):
    for j in range(i, N):
        ans = min(ans, gcd(A[i], A[j]))


print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

# A内の整数値を用いて作られる最小の整数を求めよ、という問題


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


ans = gcd(A[0], A[1])
for i in range(1, N):
    ans = min(ans, gcd(ans, A[i]))


print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))
bits = [0 for i in range(41)]
for i in range(N):
    for j in range(41):
        if A[i] & (1 << j):
            bits[41-j] += 1

bin_K = '0' * (43 - len(bin(K))) + bin(K)[2:]
x = 0
flag = 0
threshold = N // 2 + 1
for i in range(41):
    if flag == 1:
        if bits[i] < threshold:
            x += 1 << (40-i)
    elif flag == 0:
        if bits[i] < threshold and bin_K[i] == '1':
            x += 1 << (40-i)
        elif bits[i] >= threshold and bin_K[i] == '1':
            flag = 1

ans = 0
for i in range(N):
    ans += x ^ A[i]
print(ans)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
bits = [0]*41
for i in range(N):
    for j in range(41):
        if A[i] & (1 << j):
            bits[40-j] += 1


bin_K = '0' * (43 - len(bin(K))) + bin(K)[2:]
x = 0
flag = 0  # 0ならX > Kが保証されていない、1なら保証されている
threshold = N // 2 + 1
for i in range(41):
    if flag == 1:
        if bits[i] < threshold:
            x += 1 << (40-i)
    elif flag == 0:
        if bits[i] < threshold and bin_K[i] == '1':
            x += 1 << (40-i)
        elif bits[i] >= threshold and bin_K[i] == '1':
            flag = 1


ans = 0
for i in range(N):
    ans += x ^ A[i]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]

ab = np.array([x[0]-x[1] for x in AB])
sorted_ab = np.array(sorted(ab))
AB = np.array(AB)

Takahashi = 0
Aoki = 0
for i in range(N):
    if i % 2 == 0:
        t = np.where(ab == sorted_ab[0])
        T = np.array([AB[i][0] for i in list(t)[0]])
        T1 = np.where(T == max(T))
        t = list(t)[0][[list(T1)[0][0]][0]]
        Takahashi += AB[t][0]
        ab = np.delete(ab, t)
        sorted_ab = np.delete(sorted_ab, 0)
        AB = np.delete(AB, [t], axis=0)
    else:
        a = np.where(ab == sorted_ab[0])
        A = np.array([AB[i][1] for i in list(a)[0]])
        A1 = np.where(A == max(A))
        a = list(a)[0][[list(A1)[0][0]][0]]
        Aoki += AB[a][1]
        ab = np.delete(ab, a)
        sorted_ab = np.delete(sorted_ab, 0)
        AB = np.delete(AB, [a], axis=0)


print(Takahashi-Aoki)



Fixed submission:
N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]

ab = sorted([x[0]+x[1] for x in AB], reverse=True)
ans = 0
for i in range(N):
    ans -= AB[i][1]

if N % 2 == 0:
    K = N // 2
else:
    K = N // 2 + 1
for i in range(K):
    ans += ab[2*i]


print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
H = list(map(int, input().split()))


dp = [0 for _ in range(N)]
dp[1] = abs(H[1] - H[0])
# dp[i] = i+1につくまでの最小のコスト
for i in range(2, N):
    if i < K:
        A = [dp[i-k] + abs(H[i-k] - H[i]) for k in range(1, i+1)]
        dp[i] = min(A)
    else:
        A = [dp[i - k] + abs(H[i - k] - H[i]) for k in range(1, K+1)]
        dp[i] = min(A)


print(dp[-1])


Fixed submission:
N = int(input())
H = list(map(int, input().split()))


dp = [0 for _ in range(N)]
dp[1] = abs(H[1] - H[0])
# dp[i] = i+1につくまでの最小のコスト
for i in range(2, N):
    dp[i] = min((dp[i-1]+abs(H[i-1]-H[i])), (dp[i-2]+abs(H[i-2]-H[i])))


print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [0 for _ in range(N)]
dp[1] = abs(H[1] - H[0])

for i in range(2, N):
    if i < K:
        A = [dp[i-k] + abs(H[i-k] - H[i]) for k in range(1, i+1)]
        dp[i] = np.min(A)
    else:
        A = [dp[i - k] + abs(H[i - k] - H[i]) for k in range(1, K+1)]
        dp[i] = np.min(A)


print(dp[-1])

Fixed submission:
import numpy as np
N, K = map(int, input().split())
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)

for i in range(1, N):
    s = max(i-K, 0)
    dp[i] = np.min(dp[s:i]+np.abs(H[s:i]-H[i]))


print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))


dp = [0 for _ in range(N)]
dp[1] = abs(H[1] - H[0])
# dp[i] = i+1につくまでの最小のコスト
for i in range(2, N):
    if i < K:
        A = [dp[i-k] + abs(H[i-k] - H[i]) for k in range(1, i+1)]
        dp[i] = min(A)
    else:
        A = [dp[i - k] + abs(H[i - k] - H[i]) for k in range(1, K+1)]
        dp[i] = min(A)


print(dp[-1])

Fixed submission:
import numpy as np
N, K = map(int, input().split())
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)

for i in range(1, N):
    s = max(i-K, 0)
    dp[i] = np.min(dp[s:i]+np.abs(H[s:i]-H[i]))


print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                if nw < dp[nv]:
                    dp[nv] = nw
            else:
                dp[nv] = nw


print(max(dp.keys()))

Fixed submission:
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


print(dp[-1][-1])


Fixed submission:
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


print(dp[-1][-1])

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for j in range(N):
    for i in range(W + 1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])
            
  
print(dp[-1][-1])

Fixed submission:
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


print(dp[-1][-1])