Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = []
if n%2:
    flag = True
else:
    flag = False
for i in range(n):
    if (i+1)%2:
        b.append(a[i])
    else:
        b.insert(0,a[i])
if flag:
    print(*b[::-1])
else:
    print(*b)


Fixed submission:
from collections import deque
n = int(input())
a = list(map(str, input().split()))
b = deque()
if n%2:
    flag = False
else:
    flag = True
for i in range(n):
    if flag:
        if (i+1)%2:
            b.append(a[i])
        else:
            b.appendleft(a[i])
    else:
        if (i+1)%2:
            b.appendleft(a[i])
        else:
            b.append(a[i])
res = list(b)
print(' '.join(res))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = []
if n%2:
    flag = True
else:
    flag = False
for i in range(n):
    if (i+1)%2:
        b.append(a[i])
    else:
        b.insert(0,a[i])
if flag:
    print(*b[::-1])
else:
    print(*b)

Fixed submission:
from collections import deque
n = int(input())
a = list(map(str, input().split()))
b = deque()
if n%2:
    flag = False
else:
    flag = True
for i in range(n):
    if flag:
        if (i+1)%2:
            b.append(a[i])
        else:
            b.appendleft(a[i])
    else:
        if (i+1)%2:
            b.appendleft(a[i])
        else:
            b.append(a[i])
res = list(b)
print(' '.join(res))
Buggy python submission (verdict: Runtime Error):
S = list(input())
res = len(S)
kind_all = set(S)
for i in kind_all:
    temp = S.split(i)
    cnt = 0
    for j in temp:
        cnt = max(cnt,len(j))
    res = min(res,cnt)
print(res)

Fixed submission:
S = input()
res = len(S)
kind_all = set(S)
for i in kind_all:
    temp = S.split(i)
    cnt = 0
    for j in temp:
        cnt = max(cnt,len(j))
    res = min(res,cnt)
print(res)
Buggy python submission (verdict: Runtime Error):
N,K = map(int, input().split())
A = []
ruiseki = [0]
for i in range(N):
    a,b = map(int, input().split())
    A.append(a)
    ruiseki.append(ruiseki[i]+b)
K = ruiseki[-1]-K+1
for i in range(1,N+1):
    if K >= ruiseki[i]:
        n = i
        break
print(A[n+1])

Fixed submission:
N,K = map(int, input().split())
A = []
for i in range(N):
    a,b = map(int, input().split())
    A.append((a,b))
A.sort()
for i in range(N):
    K -= A[i][1]
    if K <= 0:
        print(A[i][0])
        exit()
Buggy python submission (verdict: Runtime Error):
A,B = map(int, input().split())
if A > B:
    print("GREATER")
elif A == B:
    print("EQUAL")
else:
    print("LESS")

Fixed submission:
A = int(input())
B = int(input())
if A > B:
    print("GREATER")
elif A == B:
    print("EQUAL")
else:
    print("LESS")
Buggy python submission (verdict: Runtime Error):
N  = int(input())
A = list(map(int, input().split()))
status = 0 # 0 = defalt, 1 = up, 2 = down
cnt = 1
for i in range(1,N):
    if A[i-1] < A[i]: #up petern
        if status == 0 or status == 1:
            status = 1
        else:
            status = 0
            cnt += 1
    elif A[i-1] > A[i]:
        if status == 0 or status == 2
                status = 2
        else:
            status = 0
            cnt += 1
    else:
        continue
print(cnt)

Fixed submission:
N  = int(input())
A = list(map(int, input().split()))
status = 0 # 0 = defalt, 1 = up, 2 = down
cnt = 1
for i in range(1,N):
    if A[i-1] < A[i]: #up petern
        if status == 0 or status == 1:
            status = 1
        else:
            status = 0
            cnt += 1
    elif A[i-1] > A[i]:
        if status == 0 or status == 2:
            status = 2
        else:
            status = 0
            cnt += 1
    else:
        continue
print(cnt)

Buggy python submission (verdict: Runtime Error):
N  = int(input())
A = list(map(int, input().split()))
status = 0 # 0 = defalt, 1 = up, 2 = down
cnt = 1
for i in range(1,N):
    if A[i-1] < A[i]: #up petern
        if status == 0 or status == 1:
            status = 1
        else status == 2:
            status = 0
            cnt += 1
    elif A[i-1] > A[i]:
        if status == 0 or status == 2
                status = 2
        else status:
            status = 0
            cnt += 1
    else:
        continue
print(cnt)

Fixed submission:
N  = int(input())
A = list(map(int, input().split()))
status = 0 # 0 = defalt, 1 = up, 2 = down
cnt = 1
for i in range(1,N):
    if A[i-1] < A[i]: #up petern
        if status == 0 or status == 1:
            status = 1
        else:
            status = 0
            cnt += 1
    elif A[i-1] > A[i]:
        if status == 0 or status == 2:
            status = 2
        else:
            status = 0
            cnt += 1
    else:
        continue
print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split())
if sum(A)%2:
    print("NO")
else:
    print("YES")

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
if sum(A)%2:
    print("NO")
else:
    print("YES")

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(input())
if sum(A)%2:
    print("NO")
else:
    print("YES")

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
if sum(A)%2:
    print("NO")
else:
    print("YES")
Buggy python submission (verdict: Time Limit Exceeded):
K,S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k == S:
                cnt += 1
print(cnt)

Fixed submission:
K,S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        z = S-(i+j)
        if 0 <= z <= K:
            cnt += 1
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
K,S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k == S:
                cnt += 1
print(cnt)

Fixed submission:
K,S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        z = S-(i+j)
        if 0 <= z <= K:
            cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans = 1

for i in a:
    if i == 0:
        ans = 0
        break
    ans = ans * i

if ans // (10 ** 18 + 1) != 0:
    ans = -1
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans = 1
flg = 0
max = 10 ** 18 + 1

for i in range(n):
    if a[i] == 0:
        ans = 0
        break
    if flg == 0:
        ans = ans * a[i]
    if ans // max > 0:
        ans = -1
        flg = 1

if flg != 0 and ans != 0:
    ans = -1

print(ans)
Buggy python submission (verdict: Runtime Error):
import math
from sys import exit

n=int(input())
primes = {}
i = 2
ans = 0
square = math.floor(math.sqrt(n))

if n == 1:
    print(0)
    exit()

while True:
    if i > square:
        break
    if n % i == 0:
        if i not in primes.keys():
            primes[i] = 1
        else:
            primes[i] += 1
        n = n // i
    else:
        if i == 2:
            i += 1
        else:
            i += 2
        continue

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])

#     if temp!=1:
#         arr.append([temp, 1])

#     if arr==[]:
#         arr.append([n, 1])

#     return arr

# primes = factorization(n)
if len(primes) == 0:
    print(1)
    exit()

for k,v in primes:
    base = v * 2
    root = math.floor(math.sqrt(base))
    if root * (root + 1) > base:
        root -= 1
    ans += root

print(ans)

Fixed submission:
import math
from sys import exit

n=int(input())
primes = {}
i = 2
ans = 0
square = math.floor(math.sqrt(n))

if n == 1:
    print(0)
    exit()

# while True:
#     if n == 1 or i > square:
#         break
#     if n % i == 0:
#         if i not in primes.keys():
#             primes[i] = 1
#         else:
#             primes[i] += 1
#         n = n // i
#     else:
#         if i == 2:
#             i += 1
#         else:
#             i += 2
#         continue

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

primes = factorization(n)
if len(primes) == 0:
    print(1)
    exit()

for k,v in primes:
    base = v * 2
    root = math.floor(math.sqrt(base))
    if root * (root + 1) > base:
        root -= 1
    ans += root

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int,input().split())
h = list(map(int,input().split()))

good = [i for i in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    if h[a-1] <= h[b-1] and a-1 in good:
        good.remove(a-1)
    if h[b-1] <= h[a-1] and b-1 in good:
        good.remove(b-1)

print(len(good))

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

rem_list = []

for i in range(m):
    a, b = map(int,input().split())
    if h[a-1] <= h[b-1]:
        rem_list.append(a-1)
    if h[b-1] <= h[a-1]:
        rem_list.append(b-1)

print(n-len(set(rem_list)))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int,input().split())
h = list(map(int,input().split()))

good = [i for i in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    if h[a-1] <= h[b-1] and a-1 in good:
        good.remove(a-1)
    if h[b-1] <= h[a-1] and b-1 in good:
        good.remove(b-1)

print(len(good))

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

rem_list = []

for i in range(m):
    a, b = map(int,input().split())
    if h[a-1] <= h[b-1]:
        rem_list.append(a-1)
    if h[b-1] <= h[a-1]:
        rem_list.append(b-1)

print(n-len(set(rem_list)))
Buggy python submission (verdict: Runtime Error):
x = int(input())
a = []

for i in range(100):
    num = i ** 5
    a.append(num)

for i in range(100):
    for j in range(i, 100):
        if a[i] - a[j] == x:
            ans = str(i) + ' ' + str(j)
        elif a[i] + a[j] == x:
            ans = str(i) + ' -' + str(j)
        elif a[j] - a[i] == x:
            ans = '-' + str(i) + ' -' + str(j)

print(ans)
            


Fixed submission:
x = int(input())
a = []

for i in range(500):
    num = i ** 5
    a.append(num)

for i in range(500):
    for j in range(i, 500):
        if a[i] - a[j] == x:
            ans = str(i) + ' ' + str(j)
            break
        elif a[i] + a[j] == x:
            ans = str(i) + ' -' + str(j)
            break
        elif a[j] - a[i] == x:
            ans = '-' + str(i) + ' -' + str(j)
            break

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

a,b,c,d = map(int,input().split())
if (math.ceil(a/d)) <= (math.ceil(b/c)):
    print('No')
else:
    print('Yes')


Fixed submission:
a, b = map(int,input().split())
if a <= b:
    print('unsafe')
else:
    print('safe')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))

for i in range(N):
    print(A.count(i+1))

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

sorted(A)
ans = [0] * N

for j in range(N-1):
    i = A[j] - 1
    ans[i] += 1

for i in range(N):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations_with_replacement
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

sum = 0
k = int(input())

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            sum += gcd(a,b,c)

print(sum)

Fixed submission:
from itertools import combinations_with_replacement
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

sum = 0
k = int(input())
l = range(1,k+1)

for a,b,c in combinations_with_replacement(l, 3):
    ans = gcd(a,b,c)
    if a == b and a == c:
        sum += ans
    elif a == b or b == c or c == a:
        sum += 3 * ans
    else:
        sum += 6 * ans

print(sum)
Buggy python submission (verdict: Runtime Error):
k, n = map(int,input().split())
a = list(map(int,input().split()))

end = a[0] + k - a[n-1]
b = []
b.append(end)

for i in range(0,n-1):
    diff = a[i+1] - a[i]
    b.append(diff)

b.sort(reverse=True)
print(k-max)

Fixed submission:
k, n = map(int,input().split())
a = list(map(int,input().split()))

end = a[0] + k - a[n-1]
b = []
b.append(end)

for i in range(0,n-1):
    diff = a[i+1] - a[i]
    b.append(diff)

b.sort(reverse=True)
max = b[0]
print(k-max)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, x, y = map(int,input().split())
ans = np.zeros(n-1, dtype=np.int)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            if short < dist:
                dist = short
        ans[dist-1] = ans[dist-1] + 1

for k in ans:
    print(k)

Fixed submission:
n, x, y = map(int,input().split())
ans = [0]*(n-1)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            dist = min(dist, short)
        ans[dist-1] += 1

for k in ans:
    print(k)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, x, y = map(int,input().split())
ans = np.zeros(n-1)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            if short < dist:
                dist = short
        ans[dist-1] = ans[dist-1] + 1

for k in ans:
    print(int(k))

Fixed submission:
n, x, y = map(int,input().split())
ans = [0]*(n-1)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            dist = min(dist, short)
        ans[dist-1] += 1

for k in ans:
    print(k)
Buggy python submission (verdict: Runtime Error):
import math

def count_index(list, k):
    count = 0
    for i in range(k):
        if (list[i] < list[k]):
            count = count + 1
    return list[k]-count-1

n = int(input())-1
p = list(map(int,input().split()))
q = list(map(int,input().split()))

a = (p[0]-1) * math.factorial(n)+1
b = (q[0]-1) * math.factorial(n)+1

for i in range(1,n):
    a = a + count_index(p, i) * math.factorial(n-i)
    b = b + count_index(q, i) * math.factorial(n-i)

ans = a-b
print(abs(ans))

Fixed submission:
k, x =map(int,input().split())

if k * 500 >= x:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
import math
n,k = map(int,input().split())

def ncr(n,r):
    f = math.factorial
    return (f(n) // f(r) // f(n-r))


for i in range(1,k+1):
    print(ncr(n-k+1, i) * ncr(k-1,i-1) % (10**9+7))

Fixed submission:
import math
n,k = map(int,input().split())

def ncr(n,r):
    f = math.factorial
    return (f(n) // f(r) // f(n-r))


for i in range(1,k+1):
    if n-k+1 < i:
        print(0)
    else:
        print(ncr(n-k+1, i) * ncr(k-1,i-1) % (10**9+7))
Buggy python submission (verdict: Runtime Error):
from math import gcd
a,b,c,d = map(int,input().split())

lcm = c*d/gcd(c,d)
print(b - a + 1 - int(b/c) + int((a-1)/c) - int(b/d) + int((a-1)/d) + int(b/lcm) - int((a-1)/lcm))

Fixed submission:
from fractions import gcd
a,b,c,d = map(int,input().split())

lcm = c*d//gcd(c,d)
print(b - a + 1 - b//c + (a-1)//c - b//d + (a-1)//d + b//lcm - (a-1)//lcm)
Buggy python submission (verdict: Runtime Error):
from sys import exit
from collections import deque

n, m = map(int,input().split())
a = deque(int(input()) for i in range(m))

base = a.popleft()
p = 10 ** 9 + 7

dp = [1] * (n+1)

if base == 0:
    print(0)
    exit()

for i in range(1, n+1):
    if base == i:
        dp[i] = 0
        if len(a) != 0:
            base = a.popleft()
        continue
    if i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % p
    if dp[i] == 0:
        print(0)
        exit()

print(dp[n])

Fixed submission:
from sys import exit
from collections import deque

n, m = map(int,input().split())
a = deque(int(input()) for i in range(m))

if len(a) != 0:
    base = a.popleft()
else:
    base = -1

p = 10 ** 9 + 7

dp = [1] * (n+1)

if base == 0:
    print(0)
    exit()

for i in range(1, n+1):
    if base == i:
        dp[i] = 0
        if len(a) != 0:
            base = a.popleft()
        continue
    if i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % p
    if dp[i] == 0:
        print(0)
        exit()

print(dp[n])
Buggy python submission (verdict: Runtime Error):
N,A,B,C,D = map(int,input().split())
S = list(input())

flg = 0

if C < D:
   cnt = 0
    for i in range(A, D):
        if S[i] == '#':
            cnt += 1
        else:
            cnt = 0
        if cnt == 2:
            flg = 1
            break

else:
    cnt = 0
    flg = 1
    for i in range(B-1, D+1):
        if S[i] == '.':
            cnt += 1
        else:
            cnt = 0
        if cnt == 3:
            flg = 0
            break
if flg == 1:
    print('No')
else:
    print('Yes')

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

flg = 0
cnt = 0
S_ac = S[A:C]
S_bd = S[B:D]

if '##' in S_ac or '##' in S_bd:
    flg = 1

if D < C and flg == 0:
    S = S[B-2:D+1]
    if '...' not in S:
        flg = 1

if flg == 1:
    print('No')
else:
    print('Yes')
Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc = sorted(bc, key = lambda x : x[1], reverse=True)

sum_b = 0
for b, c in bc:
    sum_b += b
    a += [c] * b
    print(a)
    if n < sum_b:
        break
a.sort(reverse=True)
a = a[:n]

print(sum(a))

Fixed submission:
n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc = sorted(bc, key = lambda x : x[1], reverse=True)

sum_b = 0
for b, c in bc:
    sum_b += b
    a += [c] * b
    if n < sum_b:
        break
a.sort(reverse=True)
a = a[:n]

print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
b, c = [list(i) for i in zip(*bc)]

sum_b = sum(b)

for i in range(m):
    add = [c[i] for _ in range(b[i])]
    a.extend(add)
a.sort()
a = a[sum_b:]


print(sum(a))

Fixed submission:
n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc = sorted(bc, key = lambda x : x[1], reverse=True)

sum_b = 0
for b, c in bc:
    sum_b += b
    a += [c] * b
    if n < sum_b:
        break
a.sort(reverse=True)
a = a[:n]

print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
b, c = [list(i) for i in zip(*bc)]

sum_b = sum(b)

for i in range(m):
    add = [c[i] for _ in range(b[i])]
    a.extend(add)
a.sort()
a = a[sum_b:]


print(sum(a))

Fixed submission:
n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc = sorted(bc, key = lambda x : x[1], reverse=True)

sum_b = 0
for b, c in bc:
    sum_b += b
    a += [c] * b
    if n < sum_b:
        break
a.sort(reverse=True)
a = a[:n]

print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')

dp = [INF] * n
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,n):
    for j in range(1,min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')

dp = [INF] * n
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,n):
    for j in range(1,min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]

    dp = [list([0] * (W+1)) for _ in range(N)]
    dp[0][wv[0][0]] = wv[0][1]

    for i in range(1,N):
        w = wv[i][0]
        if W < w:
            continue
        v = wv[i][1]
        for j in range(W+1):
            sum_w = j + w
            if sum_w <= W:
                dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][j] + v)
            dp[i][j] = max(dp[i][j],dp[i-1][j])

    print(max(dp[-1]))

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]

    dp = [list([0] * (W+1)) for _ in range(N)]
    dp[0][wv[0][0]] = wv[0][1]

    for i in range(1,N):
        w = wv[i][0]
        if W < w:
            continue
        v = wv[i][1]
        for j in range(W+1):
            sum_w = j + w
            if sum_w <= W:
                dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][j] + v)
            dp[i][j] = max(dp[i][j],dp[i-1][j])

    print(max(dp[-1]))

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]

    dp = [list([0] * (W+1)) for _ in range(N)]
    dp[0][wv[0][0]] = wv[0][1]

    for i in range(1,N):
        w = wv[i][0]
        if W < w:
            continue
        v = wv[i][1]
        for j in range(W+1):
            sum_w = j + w
            if sum_w <= W:
                dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][j] + v)
            dp[i][j] = max(dp[i][j],dp[i-1][j])

    print(max(dp[-1]))

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]

    INF = float('inf')
    dp = [list([INF] * (10 ** 5 + 101)) for _ in range(N)]
    dp[0][wv[0][1]] = wv[0][0]
    dp[0][0] = 0

    for i in range(1,N):
        w = wv[i][0]
        v = wv[i][1]
        for j in range(10 ** 5 + 1):
            sum_v = j + v
            if dp[i-1][j] + w <= W:
                dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][j] + w)
            dp[i][j] = min(dp[i][j], dp[i-1][j])
    
    max_v = 0
    for i in range(10 ** 5 + 1):
        if dp[N-1][i] <= W:
            max_v = i
    print(max_v)

if __name__ == "__main__":
    main()