Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(K):
        b = [0] * (N+1)
        for j in range(N):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        b = b[:N]
        if b == A:
            break
        else:
            A = b
    print(*A)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(K):
        b = [0] * (N+1)
        for j in range(N):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        b = b[:N]
        if b == A:
            break
        else:
            A = b
    print(*A)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(K):
        b = [0] * (N+1)
        for j in range(N):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        if b == A:
            break
        else:
            A = b[:N]
    print(*A)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(K):
        b = [0] * (N+1)
        for j in range(N):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        b = b[:N]
        if b == A:
            break
        else:
            A = b
    print(*A)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    flag = True
    D = 0
    now = 1
    LOG = {}
    PATH = []
    for i in range(N):
        PATH.append(D)
        LOG.setdefault(D,i)

        if LOG[D] == i:
            D = A[D]-1
            continue
        else:
            print("break",D)
            start = D
            break
        # print(PATH, D)
    K = K%i
    LAST = PATH[LOG[D] + K] +1
    print(LAST)



if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    D = 1
    LOG = {}
    PATH = []
    for i in range(N):
        PATH.append(D)
        LOG.setdefault(D,i)

        if LOG[D] == i:
            D = A[D-1]
            # print(PATH,LOG, i)
            continue
        else:
            # print("break",D, i)
            break

    # if i-LOG[D] < K:
    if LOG[D] < K:
        K = (K-i)%(i-LOG[D])
        LAST = PATH[LOG[D]+K]
    else:
        LAST = PATH[K]
    print(LAST)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
    N, M, Q = map(int, input().split())
    R = [list(map(int, input().split())) for i in range(Q)]
    ARR = [0]*N
    SUM = 0
    ANS = 0
    for i in nums:
        if ARR[R[i][0]-1] != 0:
            A = ARR[R[i][0]-1] 
        else:
            ARR[R[i][0]-1] = 1 
            A = ARR[R[i][0]-1] 
        if ARR[R[i][1]-1] != 0:
            B = ARR[R[i][1]-1]
        else:
            ARR[R[i][1]-1] = ARR[R[i][0]-1] + R[i][2]
        if ARR[R[i][1]-1]-ARR[R[i][0]-1] == R[i][2]:
            SUM += R[i][3]
        if max(ARR) - min(ARR) <= M:
            ANS = max(ANS, SUM)
        SUM = 0
    print(ANS)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque
ANS = 0
SUM = 0
def dfs(arr, l):
    global SUM, ANS
    # print(arr)
    if l == N:
        for i in range(Q):
            # print(arr[A[i][1]-1]-arr[A[i][0]-1])

            if arr[A[i][1]-1]-arr[A[i][0]-1] == A[i][2]:
                SUM += A[i][3]
            ANS = max(SUM, ANS)
        SUM = 0
        return
    else:
        for i in range(arr[l-1], M+1):
            arr.append(i)
            l = len(arr)
            # print(arr)
            dfs(arr,l)
            arr.pop()

    return ANS

if __name__ == '__main__':
    N, M ,Q = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(Q)]
    ARR = deque([1])
    dfs(ARR,1)
    print(ANS)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
   K = int(input())
   CNT = 0
   for i in range(1, K+1):
       for j in range(1, K+1):
           A = gcd(i, j)
           for k in range(1, K+1):
               CNT += gcd(A, k)
   print(CNT)

def gcd(p, q):
    if p%q == 0:
        return q
    return gcd(q, p%q)

if __name__ == '__main__':
    main()

Fixed submission:
import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        GCD = gcd(i,j)
        if GCD == 1:
            CNT += K
        else:
            for k in range(1, K+1):
                if gcd(GCD,k) != 1:
                    CNT += gcd(GCD,k)
                else:
                    CNT += 1
print(CNT)

Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
input = sys.stdin.readline
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            CNT += gcd(i,j,k)
print(CNT)

Fixed submission:
import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        GCD = gcd(i,j)
        if GCD == 1:
            CNT += K
        else:
            for k in range(1, K+1):
                if gcd(GCD,k) != 1:
                    CNT += gcd(GCD,k)
                else:
                    CNT += 1
print(CNT)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            CNT += gcd(i,j,k)
print(CNT)

Fixed submission:
import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        GCD = gcd(i,j)
        if GCD == 1:
            CNT += K
        else:
            for k in range(1, K+1):
                if gcd(GCD,k) != 1:
                    CNT += gcd(GCD,k)
                else:
                    CNT += 1
print(CNT)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
CNT = 0
for i in range(N):
    for j in range(i,N):
        if S[j] != S[i]:
            for k in range(j,N):
                if S[k] != S[i] and S[k] != S[j] and j-i != k-j:
                    CNT += 1
print(CNT)

Fixed submission:
N = int(input())
S = input()
CNTR = 0
CNTG = 0
CNTB = 0
for i in range(N):
    if S[i] == 'R':
        CNTR += 1
    if S[i] == 'G':
        CNTG += 1
    if S[i] == 'B':
        CNTB += 1
CONB = CNTR * CNTG * CNTB
CNT = 0
for i in range(N):
    for j in range(i,N):
        if S[j] != S[i]:
            k = j + (j-i)
            if k > N-1:
                continue
            if S[k] != S[i] and S[k] != S[j]:
                CNT += 1
print(CONB - CNT)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
CNT = 0
for i in range(N):
    for j in range(i,N):
        if S[j] != S[i]:
            for k in range(j,N):
                if S[k] != S[i] and S[k] != S[j] and j-i != k-j:
                    CNT += 1
print(CNT)

Fixed submission:
N = int(input())
S = input()
CNTR = 0
CNTG = 0
CNTB = 0
for i in range(N):
    if S[i] == 'R':
        CNTR += 1
    if S[i] == 'G':
        CNTG += 1
    if S[i] == 'B':
        CNTB += 1
CONB = CNTR * CNTG * CNTB
CNT = 0
for i in range(N):
    for j in range(i,N):
        if S[j] != S[i]:
            k = j + (j-i)
            if k > N-1:
                continue
            if S[k] != S[i] and S[k] != S[j]:
                CNT += 1
print(CONB - CNT)
Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())
row = str('b')*a
while len(row) < n:
    if a == 0:
        print(0)
        break

    row += str('r')*b + str('b')*a
ans = row[0:n].count('b')
print(ans)

Fixed submission:
n, a, b = map(int, input().split())
ans = int(n/(a+b)) * a
mod = n%(a+b)
if mod != 0:
   if mod >= a:
       ans += a
   else:
       ans += mod
if a == 0:
    ans = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import collections
from numpy.ma.core import sort
N = int(input())
arr = [input() for i in range(N)]
c = collections.Counter(arr)
# print(max(c.values()))
# ans = [c[x] for x in c]
ans = sorted([x for x in c if c[x] == max(c.values())])
# ans = [x for x in c]
for i in ans:
    print(i)

Fixed submission:
import collections
N = int(input())
arr = [input() for i in range(N)]
c = collections.Counter(arr)
# print(max(c.values()))
# ans = [c[x] for x in c]
MAX = max(c.values())
ans = sorted([x for x in c if c[x] == MAX])
# ans = [x for x in c]
for i in ans:
    print(i)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = str(input())
c = 0
for i in range(len(s)):
  if s[i] == "A":
    if s[1+1] == "B" and s[i+2] == "C":
      c += 1
print(c)

Fixed submission:
n = int(input())
s = str(input())
c = 0
for i in range(n-2):
  if s[i] == "A":
    if s[i+1] == "B" and s[i+2] == "C":
      c += 1
print(c)
Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())
ans = int(A*B/math.gcd(A,B))
print(ans)

Fixed submission:
import fractions
A, B = map(int, input().split())
ans = A*B//fractions.gcd(A,B)
print(ans)

Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())
ans = int(A*B/math.gcd(A,B))
print(ans)

Fixed submission:
import fractions
A, B = map(int, input().split())
ans = A*B//fractions.gcd(A,B)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
if N%2 == 0:
  if S[:N//2+1] == [N//2:]:
    print("Yes")
  else:
    print("No")
else:
  print("No")

Fixed submission:
N = int(input())
S = input()
if N%2 == 0:
  if S[:N//2] == S[N//2:]:
    print("Yes")
  else:
    print("No")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
A, B = map(input().split())
if A<10 and B<10:
  print(A*B)
else:
  print(-1)

Fixed submission:
A, B = map(int, input().split())
if A<10 and B<10:
  print(A*B)
else:
  print(-1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
flag = false
for i in range(1,10):
  if n%i == 0 and 0 < n/i < 10:
    flag = True
    break
if flag:
  print("Yes")
else
  print("No")

Fixed submission:
n = int(input())
flag = False
for i in range(1,10):
  if n%i == 0 and 0 < n/i < 10:
    flag = True
    break
if flag:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
# C = [str(i) for j in range(1, N+1) for i in A if i == j]
C = [str(A.index(i)+1) for i in range(1,N+1)]
L = ' '.join(C)
print(L)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
# C = [str(i) for j in range(1, N+1) for i in A if i == j]
# index と　value を入れ替える
C = [0]*N
# print(C)
for k in range(N):
    C[A[k]-1] = str(k+1)
    # C[k] = k
# print(C)
# C = [str(A.index(i)+1) for i in range(1,N+1)]
L = ' '.join(C)
print(L)
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
print(max(max(A+B, A-B), A*B))

Fixed submission:
A, B = map(int, input().split())
print(max(max(A+B, A-B), A*B))
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
print(max(C - (A-B), 0)

Fixed submission:
A, B, C = map(int, input().split())
print(max(C - (A-B), 0))
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
if (A+B)%2 != 0:
    print((A+B)//2)
else:
    print("IMPOSSIBLE)

Fixed submission:
A, B = map(int, input().split())
if (A+B)%2 == 0:
    print((A+B)//2)
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = list(map(int, input().split()))
CNT = 0
for i in range(N):
  if P[i] == i+1
    CNT += 1
print('YES' if  CNT <=  2 else 'NO')

Fixed submission:
N = int(input())
P = list(map(int, input().split()))
CNT = 0
for i in range(N):
  if P[i] != i+1:
    CNT += 1
print('YES' if  CNT <=  2 else 'NO')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import math
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    MAX = max(A)
    Ms = [-1]*N
    for i in range(N):
        if A[i] == MAX:
            A[i] = 0
            Ms[i] = max(A)
            A[i] = MAX
        else:
            Ms[i] = MAX
    for i in range(N):
        print(Ms[i])

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    A = deque([int(input()) for i in range(N)])
    MAX = max(A)
    MAX2 = 0
    Ms = [-1]*N
    for i in range(N):
        if A[i] == MAX:
            if MAX2 != 0:
                Ms[i] = MAX2
            else:
                A[i] = 0
                MAX2 = max(A)
                Ms[i] = MAX2
        else:
            Ms[i] = MAX
    for i in range(N):
        print(Ms[i])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import math
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    MAX = max(A)
    Ms = [-1]*N
    for i in range(N):
        if A[i] == MAX:
            A[i] = 0
            Ms[i] = max(A)
            A[i] = MAX
        else:
            Ms[i] = MAX
    for i in range(N):
        print(Ms[i])

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    A = deque([int(input()) for i in range(N)])
    MAX = max(A)
    MAX2 = 0
    Ms = [-1]*N
    for i in range(N):
        if A[i] == MAX:
            if MAX2 != 0:
                Ms[i] = MAX2
            else:
                A[i] = 0
                MAX2 = max(A)
                Ms[i] = MAX2
        else:
            Ms[i] = MAX
    for i in range(N):
        print(Ms[i])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
S = input()
for i in range(1,5):
  if S[i] == S[i-1]:
    print('Bad')
    break
else:
  print('Good')

Fixed submission:
S = input()
for i in range(1,4):
  if S[i] == S[i-1]:
    print('Bad')
    break
else:
  print('Good')

Buggy python submission (verdict: Runtime Error):
S = input()
for i in range(1,5):
  if S[i] == S[i-1]:
    print('Bad')
    break


Fixed submission:
S = input()
for i in range(1,4):
  if S[i] == S[i-1]:
    print('Bad')
    break
else:
  print('Good')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for i in range(M)]
    ID = [True]*N
    for arrs in arr:
        L, R = arrs
        for i in range(N):
            if L-1 <= i and i < R:
                continue
            else:
                ID[i] = False
    print(ID.count(True))

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    maxL, minR = 0, N+1
    for i in range(M):
        L, R = map(int, input().split())
        maxL = max(L, maxL)
        minR = min(R, minR)
    ans = minR -maxL + 1
    print(ans if ans>0 else 0)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for i in range(M)]
    ID = [True]*N
    for arrs in arr:
        L, R = arrs
        for i in range(N):
            if L-1 <= i and i < R:
                continue
            else:
                ID[i] = False
    print(ID.count(True))

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    maxL, minR = 0, N+1
    for i in range(M):
        L, R = map(int, input().split())
        maxL = max(L, maxL)
        minR = min(R, minR)
    ans = minR -maxL + 1
    print(ans if ans>0 else 0)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    H = list(map(int, input().split()))
    CNT = 1
    if H[1] >= H[0]:
        CNT += 2
        High = H[1]
    else:
        High = H[0]
    for i in range(2,N):
        if H[i]>=H[i-1] and H[i]>=High:
            CNT += 1
    print(CNT)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    H = list(map(int, input().split()))
    if N == 1:
        return print(1)
    CNT = 1
    High = H[0]
    for i in range(1,N):
        if H[i] >= High:
            CNT += 1
            High = H[i]
        
    return print(CNT)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def gdc(p, q):
    if q <= 0:
        return p
    p -= q
    return gdc(max(p,q), min(p,q))

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A_sorted = sorted(A)
    print(gdc(A[1], A[0]))


if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def gdc(p, q):
    if q == 0:
        return p
    return gdc(q, p%q)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 1:
        print(A[0])
        return
    res = A[0]
    for i in range(1,N):
        res = gdc(res, A[i])
    print(res)

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
f_INF = float('inf')
dp = [f_INF]*N
dp[0] = 0
for i in range(N):
    for j in range(1,min(K+1, N-i)):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])

Fixed submission:
import sys
sys.setrecursionlimit(10**9) #上限を１００万回に設定

N, K = map(int, input().split())
h = list(map(int, input().split()))
f_INF = float('inf')
dp = [f_INF]*N
dp[0] = 0
for i in range(N):
    for j in range(1,min(K+1, N-i)):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9) #上限を１００万回に設定

N, K = map(int, input().split())
h = list(map(int, input().split()))
f_INF = float('inf')
dp = [f_INF]*N
dp[0] = 0
for i in range(N):
    for j in range(1,min(K+1, N-i)):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])

Fixed submission:
import sys
sys.setrecursionlimit(10**9) #上限を１００万回に設定

N, K = map(int, input().split())
h = list(map(int, input().split()))
f_INF = float('inf')
dp = [f_INF]*N
dp[0] = 0
for i in range(N):
    for j in range(1,min(K+1, N-i)):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = list(map(int, input().split()))
f_INF = float('inf')
dp = [f_INF]*2*N
dp[0] = 0
for i in range(N):
    for j in range(1,min(K+1, N-i)):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])

Fixed submission:
import sys
sys.setrecursionlimit(10**9) #上限を１００万回に設定

N, K = map(int, input().split())
h = list(map(int, input().split()))
f_INF = float('inf')
dp = [f_INF]*N
dp[0] = 0
for i in range(N):
    for j in range(1,min(K+1, N-i)):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    L = [list(map(int, input().split())) for i in range(N)]
    #もらうDP i+1が i番目を検討した結果を示す
    V = [[0]*(W+1) for i in range(N+1)]

    for i in range(N):
        w, v = L[i]
        for s in range(W+1):
            if s-w >=0:
                #選んだあとの価値
                V[i+1][s] = max(V[i+1][s], V[i][s-w] + v)
            # 選ばないときと比較
            V[i+1][s] = max(V[i+1][s], V[i][s])
    print(V[N][W])

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    # C = [list(map(int, input().split())) for i in range(N)]
    V, W = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0]*(M+1) for i in range(N+1)]
    # print(dp)
    # print(W)
    
    for i in range(N):
        for w in range(M+1):
            if w - W[i] >= 0:
               dp[i+1][w] = max(dp[i+1][w], dp[i][w-W[i]] + V[i]) 
            dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    print(dp[N][M])    


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    # C = [list(map(int, input().split())) for i in range(N)]
    V, W = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0]*(M+1) for i in range(N+1)]
    # print(dp)
    # print(W)
    
    for i in range(N):
        for w in range(M+1):
            if w - W[i] >= 0:
               dp[i+1][w] = max(dp[i+1][w], dp[i][w-W[i]] + V[i]) 
            dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    print(dp[N][M])    


if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    # C = [list(map(int, input().split())) for i in range(N)]
    V, W = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0]*(M+1) for i in range(N+1)]
    # print(dp)
    # print(W)
    
    for i in range(N):
        for w in range(M+1):
            if w - W[i] >= 0:
               dp[i+1][w] = max(dp[i+1][w], dp[i][w-W[i]] + V[i]) 
            dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    print(dp[N][M])    


if __name__ == '__main__':
    main()