Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))

    res = []
    xorSum = 0

    for i in range(0,N-1):
        xorSum ^= A[i]
    
    res.append(xorSum)

    for i in range(N-1):
        xorSum = xorSum ^ A[::-1][i] ^ A[::-1][i+1]
        res.append(xorSum)
    
    print(" ".join(map(str, res[::-1])))

if __name__ == '__main__':
    main()

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

    res = []
    xorSum = 0

    for i in range(0,N-1):
        xorSum ^= A[i]
    
    res.append(xorSum)
    A_reversed = A[::-1]

    for i in range(N-1):
        xorSum = xorSum ^ A_reversed[i] ^ A_reversed[i+1]
        res.append(xorSum)
    
    print(" ".join(map(str, res[::-1])))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    A = list(map(int, input().split()))

    A_sorted = sorted(A, reverse=True)
    flag = True
    res = 0

    for i in range(n-1):
        flag = True
        for j in range(i+1,n):
            if (A_sorted[i] % A_sorted[j] == 0):
                flag = False
                break
        
        if flag:
            res += 1
    
    if A_sorted[-2] == A_sorted[-1]:
        print(res)
    else:
        print(res+1)


if __name__ == '__main__':
    main()

Fixed submission:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    n = int(input())
    A = sorted(list(map(int, input().split())))

    multiples = [1] * (10 ** 6 + 1)

    bucket = Counter(A)
    res = 0

    for num in A:
        if bucket[num] == 1 and multiples[num] == 1:
            res += 1
        if multiples[num] == 1:
            for i in range(num, 10**6+1, num):
                multiples[i] = 0
    
    print(res)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = 1

    for num in A:
        res = res * num
    
    if res > 10 ** 18:
        print(-1)
    else:
        print(res)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = 1

    if 0 in A:
        res = 0
    else:
        for num in A:
            res = res * num
            if res > 10**18:
                res = -1
                break
    print(res)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# ABC163 C

def main():
    n = int(input())
    A = list(map(int, input().split()))

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

if __name__ == '__main__':
    main()

Fixed submission:
# ABC163 C

def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = [0] * n

    for i in A:
        res[i-1] += 1
    
    for num in res:
        print(num)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# ABC158 B

N, A, B = map(int, input().split())

column = ""

for i in range(10**100):
    if len(column) >= N:
        break
    column = column + ("b" * A) + ("r" * B)

print(column[:N].count("b"))

Fixed submission:
# ABC158 B

n, a, b = map(int, input().split())

res1 = a * (n // (a+b))

if a > n % (a+b):
    res2 = n % (a+b)
else:
    res2 = a

print(res1 + res2)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC155 C

n = int(input())
S = []

for _ in range(n):
    S.append(input())

set_S = list(set(S))
count_S = []

for string in set_S:
    count_S.append(S.count(string))

max_S = max(count_S)

index_nums = [n for n, v in enumerate(count_S) if v == max_S]
res = []

for i in index_nums:
    res.append(set_S[i])

for _ in sorted(res):
    print(_)

Fixed submission:
# ABC155 C

n = int(input())
S = {}
max_S = 0
res = []

for _ in range(n):
    s = input()
    if s in S:
        S[s] += 1
        if S[s] > max_S:
            max_S = S[s]
    else:
        S[s] = 1
        if S[s] > max_S:
            max_S = S[s]

for key in S:
    if S[key] == max_S:
        res.append(key)

for _ in sorted(res):
    print(_)

Buggy python submission (verdict: Time Limit Exceeded):
# ABC155 C

n = int(input())
S = []

for _ in range(n):
    S.append(input())

set_S = list(set(S))
count_S = []

for string in set_S:
    count_S.append(S.count(string))

index_nums = [n for n, v in enumerate(count_S) if v == max(count_S)]
res = []

for i in index_nums:
    res.append(set_S[i])

for _ in sorted(res):
    print(_)

Fixed submission:
# ABC155 C

n = int(input())
S = {}
max_S = 0
res = []

for _ in range(n):
    s = input()
    if s in S:
        S[s] += 1
        if S[s] > max_S:
            max_S = S[s]
    else:
        S[s] = 1
        if S[s] > max_S:
            max_S = S[s]

for key in S:
    if S[key] == max_S:
        res.append(key)

for _ in sorted(res):
    print(_)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC 153 C

n, k = map(int, input().split())
H = list(map(int, input().split()))

for _ in range(k):
    if len(H) != 0:
        H.remove(max(H))

print(sum(H))

Fixed submission:
# ABC 153 C

n, k = map(int, input().split())
H = list(map(int, input().split()))

H.sort()

for _ in range(k):
    if len(H) != 0:
        H.pop()
    else:
        break

print(sum(H))
Buggy python submission (verdict: Time Limit Exceeded):
# ABC 152 C

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

res = 0

for i in range(N):
    if P[i] <= min(P[:i+1]):
        res += 1
    else:
        continue

print(res)

Fixed submission:
# ABC 152 C

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

res = 0
minP = 10 ** 9

for i in range(N):
    if P[i] <= minP:
        res += 1
        minP = P[i]
    else:
        continue

print(res)
Buggy python submission (verdict: Runtime Error):
# ABC148 C

import math

A, B = map(int, input().split())

print(A * B // math.gcd (A, B))

Fixed submission:
# ABC148 C

import fractions

A, B = map(int, input().split())

print(A * B // fractions.gcd (A, B))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

result = []

for i in range(N):
    ind = A.index(min(A))
    result.append(str(ind+1))
    A[ind] = N + 1

print(" ".join(result))

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

new_A = list(enumerate(A, 1))
sorted_A = sorted(new_A, key=lambda new_A:new_A[1])

for num in sorted_A:
    print(num[0], end=" ")
Buggy python submission (verdict: Runtime Error):
# ALC 005 D

N = int(input())
list_p = list(map(int, input().split()))
swapCount = 0

for i in range(N):
    if list_p[i] == i+1:
        temp = list_p[i]
        list_p[i] = list_p[i+1]
        list_p[i+1] = temp
        swapCount += 1

print(swapCount)

Fixed submission:
# ALC 005 D

N = int(input())
list_p = list(map(int, input().split()))
swapCount = 0

for i in range(N):
    if list_p[i] == i+1:
        temp = list_p[i]
        
        if i == len(list_p)-1:
            list_p[i] = list_p[i-1]
            list_p[i-1] = temp
        else:
            list_p[i] = list_p[i+1]
            list_p[i+1] = temp
        
        swapCount += 1

print(swapCount)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = 0
    i = 1

    while i < len(A) - 1:
        if (A[i - 1] < A[i] and A[i] > A[i + 1]) or (A[i - 1] > A[i] and A[i] < A[i + 1]):
            res += 1
            A = A[i + 1:]
            i = 1
        else:
            i += 1
    
    print(res + 1)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = 1
    inc = 0
    dec = 0

    for i in range(n - 1):
        if A[i] < A[i+1]:
            inc += 1
        elif A[i] > A[i+1]:
            dec += 1
        
        if inc and dec:
            res += 1
            inc, dec = 0, 0
    
    print(res)

if __name__ == '__main__':
    main()

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

    res = 0
    i = 1

    while i < len(A) - 1:
        if (A[i - 1] < A[i] and A[i] > A[i + 1]) or (A[i - 1] > A[i] and A[i] < A[i + 1]):
            res += 1
            A = A[i + 1:]
            i = 1
        else:
            i += 1
    
    print(res + 1)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = 1
    inc = 0
    dec = 0

    for i in range(n - 1):
        if A[i] < A[i+1]:
            inc += 1
        elif A[i] > A[i+1]:
            dec += 1
        
        if inc and dec:
            res += 1
            inc, dec = 0, 0
    
    print(res)

if __name__ == '__main__':
    main()

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

    res = 0
    i = 1

    while i < len(A) - 1:
        if A[i - 1] < A[i] and A[i] > A[i + 1]:
            res += 1
            A = A[i + 1:]
            i = 1
        elif A[i - 1] > A[i] and A[i] < A[i + 1]:
            res += 1
            A = A[i + 1:]
            i = 1
        else:
            i += 1
    
    print(res + 1)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = 1
    inc = 0
    dec = 0

    for i in range(n - 1):
        if A[i] < A[i+1]:
            inc += 1
        elif A[i] > A[i+1]:
            dec += 1
        
        if inc and dec:
            res += 1
            inc, dec = 0, 0
    
    print(res)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    k, s = map(int, input().split())

    res = 0

    for x in range(k+1):
        for y in range(k+1):
            for z in range(k+1):
                if x + y + z == s:
                    res += 1
    
    print(res)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    k, s = map(int, input().split())

    res = 0

    for x in range(k+1):
        for y in range(k+1):
            z = s - (x + y)
            if z <= k and z >= 0:
                res += 1
        
    print(res)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())

lis = sorted(list(map(int, input().split())))

query = []
for i in range(m):
    b, c = map(int, input().split())
    query.append([c, b])

query.sort(reverse = 1)

i = 0
for j in query:
    for k in range(j[-1]):
        if lis[i] < j[0]:
            lis[i] = j[0]
            i += 1 
        else:
            break

print(sum(lis))

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

lis = sorted(list(map(int, input().split())))

query = []
for i in range(m):
    b, c = map(int, input().split())
    query.append([c, b])

query.sort(reverse = 1)

i = 0
for j in query:
    for k in range(j[-1]):
        if i < n:
            if lis[i] < j[0]:
                lis[i] = j[0]
                i += 1 
            else:
                break
        else:
            break
        
print(sum(lis))
Buggy python submission (verdict: Runtime Error):
from math import gcd
n = int(input())
a = list(map(int, input().split()))

pre = [0]
for i in range(n - 1):
    pre.append(gcd(pre[-1], a[i]))

post = [0]
for i in range(n - 1):
    post.append(gcd(post[-1], a[n - 1 - i]))

res = 0
for i in range(n):
    res = max(gcd(pre[i], post[n - 1 - i]), res)

print(res)


Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
    
n = int(input())
a = list(map(int, input().split()))

pre = [0]
for i in range(n - 1):
    pre.append(gcd(pre[-1], a[i]))

post = [0]
for i in range(n - 1):
    post.append(gcd(post[-1], a[n - 1 - i]))

res = 0
for i in range(n):
    res = max(gcd(pre[i], post[n - 1 - i]), res)

print(res)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

ans = 0
a = A.index(max(A))
l = A[a+1:]
for i in range(1,N):
    bf = A[i-1]
    af = A[i]
    if a <= i:
        ans += max(A)*len(l)-sum(l)
        break
    elif bf > af:
        ans += bf-af

print(ans)

Fixed submission:
N = list(input())

n = [int(s) for s in N]
if sum(n) % 9 == 0:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
from math import factorial

n, m = map(int, input().split())
if n == 1 and m == 1:
    ans = 0
elif n == 1:
    ans = factorial(m) // (factorial(m - 2) * factorial(2))
elif m == 1:
    ans = factorial(n) // (factorial(n - 2) * factorial(2))
else:
    ans = factorial(n) // (factorial(n - 2) * factorial(2))
    ans += factorial(m) // (factorial(m - 2) * factorial(2))
print(ans)


Fixed submission:
from math import factorial

n, m = map(int, input().split())
if n in [0, 1] and m in [0, 1]:
    ans = 0
elif n in [0, 1]:
    ans = factorial(m) // (factorial(m - 2) * factorial(2))
elif m in [0, 1]:
    ans = factorial(n) // (factorial(n - 2) * factorial(2))
else:
    ans = factorial(n) // (factorial(n - 2) * factorial(2))
    ans += factorial(m) // (factorial(m - 2) * factorial(2))
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

a, b = map(int, input().split())
for i in range(1, 101):
    if a == math.floor(i * 0.08):
        for j in range(1, 101):
            if b == math.floor(j * 0.1):
                if i == j:
                    break
        else:
            continue
        break
else:
    print(-1)
print(j)


Fixed submission:
a, b = map(int, input().split())
for i in range(1, 1001):
    if a == int(i * 0.08) and b == int(i * 0.1):
        print(i)
        break
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
a, b = input().split()
a_w = a * int(b)
b_w = b * int(a)

if a => b:
  print(b_w)
else:
  print(a_w)

Fixed submission:
a, b = input().split()
a_w = a * int(b)
b_w = b * int(a)

if a > b:
  print(b_w)
else:
  print(a_w)
Buggy python submission (verdict: Runtime Error):
a, b, k = map(int, input().split())

if a > k:
    c = a - k
elif a + b > k:
    c = 0
    d = a + b - k
else:
    c = 0
    d = 0

print(c, d)

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

if a > k:
    c = a - k
    d = b
elif a + b > k:
    c = 0
    d = a + b - k
else:
    c = 0
    d = 0

print(c, d)

Buggy python submission (verdict: Runtime Error):
a, b, k = map(int, input().split())

if a > k:
    c = a - k
else:
    c = 0
    d = a + b - k

print(c, d)


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

if a > k:
    c = a - k
    d = b
elif a + b > k:
    c = 0
    d = a + b - k
else:
    c = 0
    d = 0

print(c, d)
Buggy python submission (verdict: Runtime Error):
a = int(input())
s = input()

if(a => 3200):
    print(s)
else:
    print('red')

Fixed submission:
a = int(input())
s = input()

if(a >= 3200):
    print(s)
else:
    print('red')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = 1
for i in range(1, n + 1):
    p = p * i
print(p % 1000000007)


Fixed submission:
import math

n = int(input())
print(math.factorial(n) % 1000000007)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
d = list(input().split())
for i in reversed(range(n, 10001)):
    for j in range(k):
        if d[j] in str(i):
            break
    else:
        ans = i
print(ans)


Fixed submission:
n, k = map(int, input().split())
d = list(input().split())
ans = 100000
for i in range(n, 100001):
    for j in range(k):
        if d[j] in str(i):
            break
    else:
        if ans > i:
            ans = i
print(ans)
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
if A + B + C == 17:
  if A == 5:
    if B + C == 12:
      print(YES)
    else:
      print(NO)
  if A == 7:
    if B + C == 10:
      print(YES)
    else:
      print(NO)
  else:
    print(NO)
else:
  print(NO)

Fixed submission:
A, B, C = map(int, input().split())
if A + B + C == 17:
  if A == 5:
    if B + C == 12:
      print("YES")
    else:
      print("NO")
  elif A == 7:
    if B + C == 10:
      print("YES")
    else:
      print("NO")
  else:
    print("NO")
else:
  print("NO")

Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
if A + B + C == 17:
  if A == 5:
    if B + C == 12:
      return YES
    else:
      return NO
  if A == 7:
    if B + C == 10:
      return YES
    else:
      return NO
  else:
    return NO
else:
  return NO

Fixed submission:
A, B, C = map(int, input().split())
if A + B + C == 17:
  if A == 5:
    if B + C == 12:
      print("YES")
    else:
      print("NO")
  elif A == 7:
    if B + C == 10:
      print("YES")
    else:
      print("NO")
  else:
    print("NO")
else:
  print("NO")

Buggy python submission (verdict: Runtime Error):
A, B, C = int(input().split().split())
array = [A, B, C]
sa = sorted[array]
if sa = [5, 5, 7]:
  return YES
else:
  return NO

Fixed submission:
A, B, C = map(int, input().split())
if A + B + C == 17:
  if A == 5:
    if B + C == 12:
      print("YES")
    else:
      print("NO")
  elif A == 7:
    if B + C == 10:
      print("YES")
    else:
      print("NO")
  else:
    print("NO")
else:
  print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
 
N , M = (int(a) for a in input().split())
stair = [1]
brake = []
for i in range(1 , M+1) :
    a = int(input())
    brake.append(a)
 
for i in range(1, N+1) :
    if i in brake :
        brake.pop(0)
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
    
print(stair[N])

Fixed submission:
# coding: utf-8
# Your code here!

import sys
 
N , M = (int(a) for a in input().split())
stair = [1]
brake = []
for i in range(0, N + 1):
    brake.append(False)
for i in range(1 , M+1) :
    a = int(input())
    brake[a] = True

for i in range(1, N+1) :
    if brake[i] :
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
         
print(stair[N])
Buggy python submission (verdict: Runtime Error):
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
i=0
kk=k
mx=0
while i<n and a[i]<=k:
    k-=a[i]
    i+=1
    mx+=1
j=0
while j<m and b[j]<=k:
    k-=b[j]
    j+=1
    mx+=1
cou=mx
while i>=0 and j<m:
    k+=a[i]
    i-=1
    cou-=1
    while j<m and b[j]<=k:
        j+=1
        k-=b[j]
        cou+=1
    mx=max(cou,mx)
print(mx)

Fixed submission:
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
i=0
mx=0
lol=0
while i<n and a[i]<=k:
    k-=a[i]
    i+=1
    mx+=1
    lol=1
j=0
while j<m and b[j]<=k:
    k-=b[j]
    j+=1
    mx+=1
cou=mx

i-=1
while i>=0 and j<m:
    k+=a[i]
    i-=1
    cou-=1
    while j<m and b[j]<=k:
        k-=b[j]
        cou+=1
        j+=1
    mx=max(cou,mx)
print(mx)

Buggy python submission (verdict: Runtime Error):
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
i=0
kk=k
mx=0
while a[i]<=k:
    k-=a[i]
    i+=1
    mx+=1
j=0
while b[j]<=k:
    k-=b[j]
    j+=1
    mx+=1
cou=mx
while i>=0 and j<m:
    k+=a[i]
    i-=1
    cou-=1
    while j<m and b[j]<=k:
        j+=1
        k-=b[j]
        cou+=1
    mx=max(cou,mx)
print(mx)

Fixed submission:
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
i=0
mx=0
lol=0
while i<n and a[i]<=k:
    k-=a[i]
    i+=1
    mx+=1
    lol=1
j=0
while j<m and b[j]<=k:
    k-=b[j]
    j+=1
    mx+=1
cou=mx

i-=1
while i>=0 and j<m:
    k+=a[i]
    i-=1
    cou-=1
    while j<m and b[j]<=k:
        k-=b[j]
        cou+=1
        j+=1
    mx=max(cou,mx)
print(mx)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
m=1
inf=10**18
lol=0
l=list(map(int,input().split()))
if 0 in l:
    print(0)
else:

    for i in l:
      m=m*i
      if(m>inf):
        lol=1
    if(lol):
      print(-1)
    else:
      print(m)

Fixed submission:
n=int(input())
m=1
inf=10**18
lol=0
l=list(map(int,input().split()))
if 0 in l:
    print(0)
else:

    for i in l:
      m=m*i
      if(m>inf):
        lol=1
        break
    if(lol):
      print(-1)
    else:
      print(m)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
m=1
inf=10**18
lol=0
l=list(map(int,input().split()))
for i in l:
  m=m*i
if(m>inf):
  print(-1)
else:
  print(m)

Fixed submission:
n=int(input())
m=1
inf=10**18
lol=0
l=list(map(int,input().split()))
if 0 in l:
    print(0)
else:

    for i in l:
      m=m*i
      if(m>inf):
        lol=1
        break
    if(lol):
      print(-1)
    else:
      print(m)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*n
for i in range(1,min(k,n)):
	dp[i]=abs(l[i]-l[0])
#print(dp)
for i in range(k,n):
  dp[i]=dp[i-1]+abs(l[i-1]-l[i])
  for j in range(k+1):
  	dp[i]=min(dp[i],dp[i-j]+abs(l[i-j]-l[i]))
#print(dp)
print(dp[n-1])
               

Fixed submission:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*n
for i in range(1,min(k,n)):
	dp[i]=abs(l[i]-l[0])
#print(dp)
for i in range(k,n):
  dp[i]=dp[i-1]+abs(l[i-1]-l[i])
  for j in range(k+1):
  	dp[i]=min(dp[i],dp[i-j]+abs(l[i-j]-l[i]))
#print(dp)
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
we=[0]*n
val=[0]*n
for i in range(n):
  ww,v=map(int,input().split())
  we[i]=ww
  val[i]=v
dp=dd(lambda:-1)
def solve(i,w,we,val):
  if(i==0 or w==0):
    return 0
  if(dp[(i,w)]!=-1):
    return dp[(i,w)]
  if(we[i-1]<=w):
    if(dp[(i-1,w-we[i-1])]!=-1):
      x=dp[(i-1,w-we[i-1])]
    else:
      x=dp[(i-1,w-we[i-1])]=solve(i-1,w-we[i-1],we,val)
    if(dp[(i-1,w)]!=-1):
      y=dp[(i-1,w)]
    else:
      y=dp[(i-1,w)]=solve(i-1,w,we,val)
    dp[(i,w)]=max(val[i-1]+x,y)
    return dp[(i,w)]
  else:
    if(dp[(i-1,w)]!=-1):
      y=dp[(i-1,w)]
    else:
      y=dp[(i-1,w)]=solve(i-1,w,we,val)
    dp[(i,w)]=y
    return dp[(i,w)]
print(solve(n,w,we,val))
#print(dp)  


Fixed submission:
import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
maxn=10000000000000000
we=[0]*n
val=[0]*n
su=0
for i in range(n):
    ww,v=map(int,input().split())
    we[i]=ww
    val[i]=v
    su+=v
dp=[maxn]*(su+1)
dp[0]=0
for i in range(n):
    for j in range(su-val[i],-1,-1):
        dp[j+val[i]]=min(dp[j+val[i]],we[i]+dp[j])
ans=0
for i in range(len(dp)):
    if(dp[i]<=w):
        ans=max(ans,i)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict as dd
n,w=map(int,input().split())
we=[0]*n
val=[0]*n
for i in range(n):
  ww,v=map(int,input().split())
  we[i]=ww
  val[i]=v
dp=dd(lambda:-1)
def solve(i,w,we,val):
  if(i==0 or w==0):
    return 0
  if(dp[(i,w)]!=-1):
    return dp[(i,w)]
  if(we[i-1]<=w):
    dp[(i,w)]=max(val[i-1]+solve(i-1,w-we[i-1],we,val),solve(i-1,w,we,val))
    return dp[(i,w)]
  else:
    dp[(i,w)]=solve(i-1,w,we,val)
    return dp[(i,w)]
print(solve(n,w,we,val))
#print(dp)  


Fixed submission:
import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
maxn=10000000000000000
we=[0]*n
val=[0]*n
su=0
for i in range(n):
    ww,v=map(int,input().split())
    we[i]=ww
    val[i]=v
    su+=v
dp=[maxn]*(su+1)
dp[0]=0
for i in range(n):
    for j in range(su-val[i],-1,-1):
        dp[j+val[i]]=min(dp[j+val[i]],we[i]+dp[j])
ans=0
for i in range(len(dp)):
    if(dp[i]<=w):
        ans=max(ans,i)
print(ans)