Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
A = [list(map(int,input().split())) for _ in range(2)]
L = [0 for _ in range(1,N)] + [1]
PL = list(itertools.permutations(L,N))
MAX = 0
for P in PL:
    now = (0,0)
    total = A[0][0]
    for p in P:
        if p == 0:
            now = (now[0],now[1]+1)
        else:
            now = (now[0]+1,now[1])
        total += A[now[0]][now[1]]
    MAX = max(MAX,total)
print(MAX)

Fixed submission:
N = int(input())
A = [list(map(int,input().split())) for _ in range(2)]
MAX = 0
for i in range(N):
    MAX = max(MAX,sum(A[0][:i+1])+sum(A[1][i:]))
print(MAX)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
count = 0
for a in A:
    b = bisect.bisect_left(B,a+1)
    if b == N:
        continue
    for i in range(b,N):
        c = bisect.bisect_left(C,B[i]+1)
        if c == N:
            continue
        count += N-c
print(count)

Fixed submission:
import bisect
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
count = 0
for b in B:
    a = bisect.bisect_left(A,b)
    c = bisect.bisect_right(C,b)
    count += a*(N-c)
print(count)
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = list(map(int,input().split()))
count = 0
for i in range(N):
    if P[i] == i+1:
        P[i],P[i+1]=P[i+1],P[i]
        count += 1
print(count)

Fixed submission:
N = int(input())
P = list(map(int,input().split()))
count = 0
for i in range(N):
    if i != N-1 and P[i] == i+1:
        P[i],P[i+1]=P[i+1],P[i]
        count += 1
if P[N-1] == N:
    count += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]
now = 1
count = 0
past = []
while True:
    if now == 2:
        print(count)
        exit()
    if A[now - 1] in past:
        print(-1)
        exit()
    count += 1
    past.append(A[now - 1])
    now = A[now - 1]

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]
if 2 not in A:
    print(-1)
    exit()
now = 1
count = 0
past = []
while True:
    if now == 2:
        print(count)
        exit()
    if count >= N:
        print(-1)
        exit()
    count += 1
    now = A[now - 1]
Buggy python submission (verdict: Runtime Error):
A = list(map(int,input().split()))
AA = sum([i%2 for i in A])
if N == 1:
    print('YES')
    exit()
if AA % 2 == 1:
    print('NO')
    exit()
print('YES') 


Fixed submission:
N = int(input())
A = list(map(int,input().split()))
AA = sum([i%2 for i in A])
if N == 1:
    print('YES')
    exit()
if AA % 2 == 1:
    print('NO')
    exit()
print('YES')
Buggy python submission (verdict: Time Limit Exceeded):
H,W,K = list(map(int,input().split()))
C = [list(input()) for _ in range(H)]

def F1(c):
    for i in range(W):
        for j in range(H-1,-1,-1):
            if c[j][i] != 'X': continue
            for k in range(j-1,-1,-1):
                if c[k][i] != 'X':
                    c[j][i], c[k][i] = c[k][i], c[j][i]
                    break
    return c

def F2(c):
    delete_sum = 0
    for i in range(H):
        for j in range(W):
            if c[i][j] == 'X': continue
            tmp = c[i][j]
            count = 1
            for k in range(j+1,W):
                if c[i][k] == tmp:
                    count += 1
                else:
                    break
            if count >= K:
                for k in range(j,W):
                    if c[i][k] == tmp:
                        delete_sum += int(c[i][k])
                        c[i][k] = 'X'
                    else:
                        break
    return c, delete_sum

MAX = 0
for i in range(H):
    for j in range(W):
        tmpC = []
        for k in range(H):
            tmpC.append(C[k][:])
        tmpC[i][j] = 'X'
        tmpC = F1(tmpC)
        point = 0
        for k in range(1000):
            tmpC, delete_sum = F2(tmpC)
            if delete_sum == 0:
                break
            tmpC = F1(tmpC)
            point += 2**k*delete_sum
        MAX = max(MAX,point)
print(MAX)

Fixed submission:
H,W,K = list(map(int,input().split()))
C = [list(input()) for _ in range(H)]

def F1(c):
    for i in range(W):
        for j in range(H-1,-1,-1):
            if c[j][i] != 'X': continue
            for k in range(j-1,-1,-1):
                if c[k][i] != 'X':
                    c[j][i], c[k][i] = c[k][i], c[j][i]
                    break
    return c

def F2(c):
    delete_sum = 0
    for i in range(H):
        for j in range(W):
            if c[i][j] == 'X': continue
            tmp = c[i][j]
            count = 1
            for k in range(j+1,W):
                if c[i][k] == tmp:
                    count += 1
                else:
                    break
            if count >= K:
                for k in range(j,W):
                    if c[i][k] == tmp:
                        delete_sum += int(c[i][k])
                        c[i][k] = 'X'
                    else:
                        break
    return c, delete_sum

MAX = 0
for i in range(H):
    for j in range(W):
        tmpC = []
        for k in range(H):
            tmpC.append(C[k][:])
        tmpC[i][j] = 'X'
        tmpC = F1(tmpC)
        point = 0
        for k in range(1000):
            tmpC, delete_sum = F2(tmpC)
            if delete_sum == 0:
                break
            tmpC = F1(tmpC)
            point += 2**k*delete_sum
        MAX = max(MAX,point)
print(MAX)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input.split())
h, w = map(int, input.split())

print((H-h)*(W-w))

Fixed submission:
a = [input() for i in range(2)]
H, W = map(int, a[0].split())
h, w = map(int, a[1].split())
print((H-h)*(W-w))
Buggy python submission (verdict: Runtime Error):
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]

count = 0
for n in range(N):
  sum = C
  for m in range(M):
    sum += b[m]*a[n][m]
  if sum > 0:
    count += 1
print(count)

Fixed submission:
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
count=0
for n in range(N):
    sum = C
    for m in range(M):
        sum += B[m]*A[n][m]
    if sum > 0:
        count+= 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                if j - i == k - j:
                    continue
                if (S[i] != S[j]) and (S[i] != S[k]) and (S[j] != S[k]):
                    ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N = int(input())
    S = input()
    R, G, B = [0] * (N + 1), [0] * (N + 1), [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        R[i], G[i], B[i] = R[i + 1], G[i + 1], B[i + 1]
        if S[i] == 'R':
            R[i] += 1
        elif S[i] == 'G':
            G[i] += 1
        else:
            B[i] += 1
    ans = 0
    for i in range(N):
        for j in range(i + 1, N - 1):
            if S[i] == S[j]:
                continue
            if j + (j - i) + 1 < N + 1:
                if S[i] + S[j] == 'RG':
                    ans += B[j + 1]
                    if B[j + (j - i) + 1] != B[j + (j - i)]:
                        ans -= 1
                elif S[i] + S[j] == 'GR':
                    ans += B[j + 1]
                    if B[j + (j - i) + 1] != B[j + (j - i)]:
                        ans -= 1
                elif S[i] + S[j] == 'RB':
                    ans += G[j + 1]
                    if G[j + (j - i) + 1] != G[j + (j - i)]:
                        ans -= 1
                elif S[i] + S[j] == 'BR':
                    ans += G[j + 1]
                    if G[j + (j - i) + 1] != G[j + (j - i)]:
                        ans -= 1
                elif S[i] + S[j] == 'GB':
                    ans += R[j + 1]
                    if R[j + (j - i) + 1] != R[j + (j - i)]:
                        ans -= 1
                elif S[i] + S[j] == 'BG':
                    ans += R[j + 1]
                    if R[j + (j - i) + 1] != R[j + (j - i)]:
                        ans -= 1
            else:
                if S[i] + S[j] == 'RG':
                    ans += B[j + 1]
                elif S[i] + S[j] == 'GR':
                    ans += B[j + 1]
                elif S[i] + S[j] == 'RB':
                    ans += G[j + 1]
                elif S[i] + S[j] == 'BR':
                    ans += G[j + 1]
                elif S[i] + S[j] == 'GB':
                    ans += R[j + 1]
                elif S[i] + S[j] == 'BG':
                    ans += R[j + 1]
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
S = deque(list(input()))
Q = int(input())

for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        S.reverse()
    else:
        if q[1] == '1':
            S.appendleft(q[2])
        else:
            S.append(q[2])
print(''.join(S))


Fixed submission:
from collections import deque
S = deque(list(input()))
Q = int(input())

flag = False
for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        flag = True if flag is False else False
    else:
        if flag is False:
            if q[1] == '1':
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if q[1] == '1':
                S.append(q[2])
            else:
                S.appendleft(q[2])

if flag is True:
    S.reverse()
print(''.join(S))
Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int, input().split())
S = input()
L_S = len(S)

count = 0
for left in range(L_S):
    for right in range(left + 1, L_S + 1):
        num = S[left:right]
        while num[0] == '0' and len(num) > 1:
            num = num[1:]
        if (int(num) % P) == 0:
            count += 1
print(count)


Fixed submission:
def main():

    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += (i + 1)
        print(ans)
        exit()

    sum_rem = [0] * N
    sum_rem[0] = int(S[N - 1]) % P
    ten = 10
    for i in range(1, N):
        a = (int(S[N - 1 - i]) * ten) % P
        sum_rem[i] = (a + sum_rem[i - 1]) % P
        ten = (ten * 10) % P

    ans = 0
    count = [0] * P
    count[0] = 1
    for i in range(N):
        ans += count[sum_rem[i]]
        count[sum_rem[i]] += 1
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int, input().split())
S = input()
L_S = len(S)

count = 0
for left in range(L_S):
    for right in range(left + 1, L_S + 1):
        num = S[left:right]
        while num[0] == '0' and len(num) > 1:
            num = num[1:]
        if (int(num) % P) == 0:
            count += 1
print(count)


Fixed submission:
def main():

    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += (i + 1)
        print(ans)
        exit()

    sum_rem = [0] * N
    sum_rem[0] = int(S[N - 1]) % P
    ten = 10
    for i in range(1, N):
        a = (int(S[N - 1 - i]) * ten) % P
        sum_rem[i] = (a + sum_rem[i - 1]) % P
        ten = (ten * 10) % P

    ans = 0
    count = [0] * P
    count[0] = 1
    for i in range(N):
        ans += count[sum_rem[i]]
        count[sum_rem[i]] += 1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100001)
N, M, K = map(int, input().split())

label = [-1] * N
n_label = [0] * N

F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, lab):
    if label[v] != -1:
        return 0
    label[v] = lab
    n_label[lab] += 1
    for n in F[v]:
        dfs(n, lab)
    return 1


# labeling
count = 0
for i in range(N):
    count += dfs(i, count)
n_label = n_label[:count]

# calc friend candidate
blocked = 0
for b in B[0]:
    if label[b] == label[0]:
        blocked += 1
print(n_label[label[0]] - 1 - len(F[0]) - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if label[b] == label[i]:
            blocked += 1
    print(n_label[label[i]] - 1 - len(F[i]) - blocked, end='')
print('')


Fixed submission:
import math

N = int(input())
print(math.ceil(N / 2))
Buggy python submission (verdict: Time Limit Exceeded):
N, A, B = map(int, input().split())


def mod_pow(a, n, m):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % m
        a = a * a % m
        n >>= 1
    return res


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


count = mod_pow(2, N, 10 ** 9 + 7) - 1
count -= cmb(N, A) % (10 ** 9 + 7)
count -= cmb(N, B) % (10 ** 9 + 7)
if count < 0:
    count += 10 ** 9 + 7
print(count)


Fixed submission:
N, A, B = map(int, input().split())
MAX = max(A, B) + 1
MOD = 1000000007
nCk = [0] * MAX
nCk[0] = 0
nCk[1] = N


def mod_pow(a, n, m):
    res = 1
    while n != 0:
        if n & 1:
            res = (res * a) % m
        n = n >> 1
        a = (a * a) % m
    return res


def mod_inv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


for i in range(2, MAX):
    nCk[i] = (nCk[i-1] * ((N-i+1) * mod_inv(i, MOD))) % MOD

count = (mod_pow(2, N, MOD) - 1 - nCk[A] - nCk[B]) % MOD
print(int(count))

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


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


count = (2 ** N) - 1
count -= cmb(N, A)
count -= cmb(N, B) 
print(count % (10 ** 9 + 7))


Fixed submission:
N, A, B = map(int, input().split())
MAX = max(A, B) + 1
MOD = 1000000007
nCk = [0] * MAX
nCk[0] = 0
nCk[1] = N


def mod_pow(a, n, m):
    res = 1
    while n != 0:
        if n & 1:
            res = (res * a) % m
        n = n >> 1
        a = (a * a) % m
    return res


def mod_inv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


for i in range(2, MAX):
    nCk[i] = (nCk[i-1] * ((N-i+1) * mod_inv(i, MOD))) % MOD

count = (mod_pow(2, N, MOD) - 1 - nCk[A] - nCk[B]) % MOD
print(int(count))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

for i in range(N-1):
    for j in range(i+1, N):
        if A[i] == A[j]:
            print('NO')
            exit()

print('YES')


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

A.sort()
for i in range(N-1):
    if A[i] == A[i+1]:
        print('NO')
        exit()

print('YES')
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

kernel = [1] * K
est = (p + 1) / 2

est_k = np.convolve(est, kernel)
print(np.max(est_k))

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

p.insert(0, 0)
for i in range(1, N+1):
    p[i] = (p[i] + 1) / 2 + p[i-1]

s = [0] * (N+1)
for i in range(N-K+1):
    s[i] = p[i+K] - p[i]

print(max(s))

Buggy python submission (verdict: Runtime Error):
import numpy as np
N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

kernel = [1] * K
est = (p + 1) / 2

est_k = np.convolve(est, kernel)
print(np.max(est_k))

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

p.insert(0, 0)
for i in range(1, N+1):
    p[i] = (p[i] + 1) / 2 + p[i-1]

s = [0] * (N+1)
for i in range(N-K+1):
    s[i] = p[i+K] - p[i]

print(max(s))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))

count = N

for i in range(N):
    for j in range(i):
        if P[i] > P[j]:
            count -= 1
            break

print(count)

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

count = 0
min_num = 2 * 10**5

for i in range(N):
    if P[i] <= min_num:
        count += 1
        min_num = P[i]

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
N_list = [str(i) for i in range(1, N + 1)]
nums = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

count = 0
for i in nums:
    for j in nums:
        cij, cji = 0, 0
        for k in N_list:
            if k[0] == i and k[-1] == j:
                cij += 1
            if k[0] == j and k[-1] == i:
                cji += 1
        count += cij * cji

print(count)

Fixed submission:
N = int(input())

Cij = [0] * 100
for i in range(1, N + 1):
    Cij[int(str(i)[0] + str(i)[-1])] += 1

count = 0
for i in range(10):
    for j in range(10):
        count += Cij[i * 10 + j] * Cij[j * 10 + i]

print(count)
Buggy python submission (verdict: Runtime Error):
import numpy as np


def main():
    N, D = map(int, input().split())
    p = [np.array(list(map(int, input().split()))) for _ in range(N)]
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            d = np.sqrt(np.sum(np.power(p[i] - p[j], 2)))
            if d % 1 == 0:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import numpy as np


def main():
    N, D = map(int, input().split())
    p = [np.array(list(map(int, input().split()))) for _ in range(N)]
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            d = np.sqrt(np.sum(np.power(p[i] - p[j], 2)))
            if d % 1 == 0:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    cards = list(range(1, N + 1))
    for i in range(M):
        L, R = map(int, input().split())
        cards = [x for x in cards if L <= x <= R]
    print(len(cards))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, M = map(int, input().split())
    L, R = 0, 1001001
    for i in range(M):
        l, r = map(int, input().split())
        L = max(L, l)
        R = min(r, R)
    print(max(0, R - L + 1))


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


N = int(input())
h = list(map(int, input().split()))
dp = [float('inf')] * N
dp[0] = 0


def rec(i):

    if dp[i] < float('inf'):
        return dp[i]

    a = rec(i-1) + abs(h[i] - h[i-1])
    if i > 1:
        a = min(a, rec(i-2) + abs(h[i] - h[i-2]))

    dp[i] = a
    return a


print(rec(N-1))


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

dp = [float('inf') for _ in range(N)]
dp[0] = 0

for i in range(N):
    if i - 1 >= 0:
        if dp[i - 1] + abs(h[i] - h[i - 1]) < dp[i]:
            dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
    if i - 2 >= 0:
        if dp[i - 2] + abs(h[i] - h[i - 2]) < dp[i]:
            dp[i] = dp[i - 2] + abs(h[i] - h[i - 2])
print(dp[N-1])

Buggy python submission (verdict: Runtime Error):
N = int(input())
h = list(map(int, input().split()))
dp = [float('inf')] * N
dp[0] = 0


def rec(i):

    if dp[i] < float('inf'):
        return dp[i]

    a = rec(i-1) + abs(h[i] - h[i-1])
    if i > 1:
        a = min(a, rec(i-2) + abs(h[i] - h[i-2]))

    dp[i] = a
    return a


print(rec(N-1))


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

dp = [float('inf') for _ in range(N)]
dp[0] = 0

for i in range(N):
    if i - 1 >= 0:
        if dp[i - 1] + abs(h[i] - h[i - 1]) < dp[i]:
            dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
    if i - 2 >= 0:
        if dp[i - 2] + abs(h[i] - h[i - 2]) < dp[i]:
            dp[i] = dp[i - 2] + abs(h[i] - h[i - 2])
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
weights, values = [], []

for _ in range(N):
    x, y = map(int, input().split())
    weights.append(x)
    values.append(y)

dp = [[-float('inf') for _ in range(W + 1)] for _ in range(N + 1)]


def dp_rec(item, w):

    if dp[item][w] > -float('inf'):
        return dp[item][w]
    if item == N:
        return 0
    if w-weights[item] >= 0:
        res = max(dp_rec(item+1, w-weights[item]) + values[item], dp_rec(item+1, w))
    else:
        res = dp_rec(item+1, w)

    dp[item][w] = res
    return res


dp_rec(0, W)
print(dp[0][W])


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

w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

# dp[in_n_items][below_w_weight] = max_value
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(W + 1):
        if j - w[i - 1] >= 0:
            if dp[i - 1][j - w[i - 1]] + v[i - 1] > dp[i - 1][j]:
                dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1]
            else:
                dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
weights, values = [], []

for _ in range(N):
    x, y = map(int, input().split())
    weights.append(x)
    values.append(y)

dp = [[-float('inf') for _ in range(W + 1)] for _ in range(N + 1)]


def dp_rec(item, w):

    if dp[item][w] > -float('inf'):
        return dp[item][w]
    if item == N:
        return 0
    if w-weights[item] >= 0:
        res = max(dp_rec(item+1, w-weights[item]) + values[item], dp_rec(item+1, w))
    else:
        res = dp_rec(item+1, w)

    dp[item][w] = res
    return res


dp_rec(0, W)
print(dp[0][W])


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

w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

# dp[in_n_items][below_w_weight] = max_value
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(W + 1):
        if j - w[i - 1] >= 0:
            if dp[i - 1][j - w[i - 1]] + v[i - 1] > dp[i - 1][j]:
                dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1]
            else:
                dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[N][W])