Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def dijkstra(adj, start, goal=None):
    n = len(adj)
    dist = [float("inf") for i in range(n)]
    prev = [float("inf") for i in range(n)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)

        if dist[src] < prov_cost:
            continue

        for dest in range(n):
            cost = adj[src][dest]
            if cost != float("inf") and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src

    if goal is not None:
        return get_path(goal, prev)
    else:
        return dist

def get_path(goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != float("inf"):
        path.append(prev[dest])
        dest = prev[dest]
    return list(reversed(path))

n, m = map(int, input().split())
adj = [[float("inf") for i in range(n)] for i in range(n)]
path = []
for i in range(m):
    a, b, c = map(int, input().split())
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
    path.append(set([a - 1, b - 1]))
for i in range(n):
    for j in range(n):
        if i != j:
            saitan = dijkstra(adj, i, j)
            for k in range(len(saitan) - 1):
                ss = set(saitan[k:k + 2])
                if ss in path:
                    path.remove(ss)
print(len(path))

Fixed submission:
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = []
for i in range(n):
     shortest.append(dijkstra(adj, n, i))
ans = 0
for i in range(n):
    for cost, j in adj[i]:
        if cost > shortest[i][j]:
            ans += 1
print(ans // 2)
Buggy python submission (verdict: Runtime Error):
import numpy as np

x, y = map(int, input().split())
if abs(x) == abs(y):
    print(1)
elif np.sign(x) == np.sign():
    if x < y:
        print(y - x)
    else:
        print(x - y + 2)
else:
    print(x + y + 1)

Fixed submission:
x, y = map(int, input().split())
res = float("inf")
if x <= y:  # xx
    res = min(res, y - x)
if -x <= y:  # ox
    res = min(res, y + x + 1)
if x <= -y:  # xo
    res = min(res, -y - x + 1)
if -x <= -y:  # oo
    res = min(res, -y + x + 2)
print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
t = list(map(int, input().split()))
m = int(input())
s = sum(t)
for i in range(m):
  p, x = map(int, input().split())
  print(s - t[p - 1] + x)

Fixed submission:
a, op, b = input().split()
if op == "+":
  print(int(a) + int(b))
else:
  print(int(a) - int(b))
Buggy python submission (verdict: Runtime Error):
c = input()
vowel = ["a", "e", "i", "o", "u"]
if vowel.find(c) == -1:
  print("consonant")
else:
  print("vowel")

Fixed submission:
c = input()
vowel = ["a", "e", "i", "o", "u"]
if c in vowel:
  print("vowel")
else:
  print("consonant")
Buggy python submission (verdict: Time Limit Exceeded):
a, b, x = map(int, input().split())
ans = 0
for i in range(a, b + 1):
    if i % x == 0:
        ans += 1
print(ans)

Fixed submission:
a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
ans = 0
while len(set(s)) > 1:
    if s[-1] == "W":
        b = s.rfind("B") + 1
        s = s[:b] + "B" * (len(s[b:]) + 1)
    else:
        b = s.rfind("W") + 1
        s = s[:b] + "W" * (len(s[b:]) + 1)
    ans += 1
print(ans)

Fixed submission:
s = input()
ans = 0
for i in range(len(s) - 1):
    if s[i] != s[i + 1]:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()
if "F" in s[s.index("C"):]:
    print("Yes")
else:
    print("No")

Fixed submission:
s = input()
if "C" in s:
    if "F" in s[s.index("C"):]:
        print("Yes")
        exit()
print("No")
Buggy python submission (verdict: Runtime Error):
def ceil(x, y):
    if x % y == 0:
        return x // y
    else:
        return x // y + 1

n = int(input())
t = a = 1
for i in range(n):
    T, A = map(int, input().split())
    n = max(ceil(t / T), ceil(a / A))
    t = n * T
    a = n * A
print(t + a)

Fixed submission:
def ceil(x, y):
    if x % y == 0:
        return x // y
    else:
        return x // y + 1

n = int(input())
t = a = 1
for i in range(n):
    T, A = map(int, input().split())
    n = max(ceil(t, T), ceil(a, A))
    t = n * T
    a = n * A
print(t + a)
Buggy python submission (verdict: Time Limit Exceeded):
n, a = map(int, input().split())
x = list(map(int, input().split()))

ans = 0
for bit in range(1 << n):

    s = 0
    count = 0
    for i in range(n):
        if bit & (1 << i):
            s += x[i]
            count += 1

    if count and s / count == a:
        ans += 1

print(ans)

Fixed submission:
import collections

n, a = map(int, input().split())
X = [int(i) - a for i in input().split()]
ans = 0
sums = collections.Counter([0, X[0]])
for i in X[1:]:
    sums2 = collections.Counter()
    for s, c in sums.items():
        sums2[s + i] += c
    sums += sums2
print(sums[0] - 1)
Buggy python submission (verdict: Runtime Error):
def solve(s, a, b):
    if a % b == 0:
        return s + ((a // b) * 2 - 1) * b
    if b % a == 0:
        return s + ((b // a) * 2 - 1) * a
    if a == b:
        return s + a
    elif a > b:
        return solve(s + b * 2, a - b, b)
    else:
        return solve(s + a * 2, a, b - a)

n, x = map(int, input().split())
print(solve(n, n - x, x))

Fixed submission:
def solve(s, a, b):
    if a % b == 0:
        return s + ((a // b) * 2 - 1) * b
    if b % a == 0:
        return s + ((b // a) * 2 - 1) * a
    elif a > b:
        s += (a // b) * 2 * b
        return solve(s, a % b, b)
    else:
        s += (b // a) * 2 * a
        return solve(s, a, b % a)

n, x = map(int, input().split())
print(solve(n, n - x, x))

Buggy python submission (verdict: Runtime Error):
def solve(s, a, b):
    if a == 1:
        return s + b * 2 - 1
    if b == 1:
        return s + a * 2 - 1
    if a == b:
        return s + a
    elif a > b:
        return solve(s + b * 2, a - b, b)
    else:
        return solve(s + a * 2, a, b - a)

n, x = map(int, input().split())
print(solve(n, n - x, x))

Fixed submission:
def solve(s, a, b):
    if a % b == 0:
        return s + ((a // b) * 2 - 1) * b
    if b % a == 0:
        return s + ((b // a) * 2 - 1) * a
    elif a > b:
        s += (a // b) * 2 * b
        return solve(s, a % b, b)
    else:
        s += (b // a) * 2 * a
        return solve(s, a, b % a)

n, x = map(int, input().split())
print(solve(n, n - x, x))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000000)

def solve(s, a, b):
    if a == b:
        return s + a
    elif a > b:
        return solve(s + b * 2, a - b, b)
    else:
        return solve(s + a * 2, a, b - a)


n, x = map(int, input().split())
print(solve(0, n - x, x) + n)

Fixed submission:
def solve(s, a, b):
    if a % b == 0:
        return s + ((a // b) * 2 - 1) * b
    if b % a == 0:
        return s + ((b // a) * 2 - 1) * a
    elif a > b:
        s += (a // b) * 2 * b
        return solve(s, a % b, b)
    else:
        s += (b // a) * 2 * a
        return solve(s, a, b % a)

n, x = map(int, input().split())
print(solve(n, n - x, x))

Buggy python submission (verdict: Runtime Error):
def solve(s, a, b):
    if a == b:
        return s + a
    elif a > b:
        return solve(s + b * 2, a - b, b)
    else:
        return solve(s + a * 2, a, b - a)


n, x = map(int, input().split())
print(solve(0, n - x, x) + n)

Fixed submission:
def solve(s, a, b):
    if a % b == 0:
        return s + ((a // b) * 2 - 1) * b
    if b % a == 0:
        return s + ((b // a) * 2 - 1) * a
    elif a > b:
        s += (a // b) * 2 * b
        return solve(s, a % b, b)
    else:
        s += (b // a) * 2 * a
        return solve(s, a, b % a)

n, x = map(int, input().split())
print(solve(n, n - x, x))
Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import lru_cache


@lru_cache(maxsize=None)
def gcd(a, b):
    return math.gcd(a, b)


K = int(input())

total = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += gcd(gcd(a, b), c)

print(total)


Fixed submission:
import sys
import math
from functools import lru_cache

gcd = [[0] * 201 for _ in range(201)]

for i in range(201):
    for j in range(201):
        gcd[i][j] = math.gcd(i, j)

K = int(input())

total = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += gcd[gcd[a][b]][c]

print(total)
Buggy python submission (verdict: Runtime Error):
from collections import Counter


N = int(input())
S = input()

# 等間隔に並んでいる
count = 0

for start in range(N):
  offset = 1
  while True: 
      middle = start + offset
      end = middle + offset

      if end >= N:
          break

      s = {S[start], S[middle], S[end]}

      if len(s) == 3:
          count += 1

      offset += 1


x, y, z = Counter(S).values()

print(x * y * z - count)


Fixed submission:
from collections import Counter


N = int(input())
S = input()

# 等間隔に並んでいる
count = 0

for start in range(N):
  offset = 1
  while True: 
      middle = start + offset
      end = middle + offset

      if end >= N:
          break

      s = {S[start], S[middle], S[end]}

      if len(s) == 3:
          count += 1

      offset += 1

c = Counter(S)

if len(c) != 3:
  print(0)
else:  
  x, y, z = c.values()
  print(x * y * z - count)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

S = input()
Q = int(input())

deq = deque(S)

for _ in range(Q):
  q = input()
  if q == '1':
    deq.reverse()
  else:
    _, f, c = q.split()
    if f == '1':
      deq.appendleft(c)
    else:
      deq.append(c)

print(''.join(deq))


Fixed submission:
from collections import deque

S = input()
Q = int(input())

deq = deque(S)

direction = 1

for _ in range(Q):
  q = input()
  if q == '1':
    direction *= -1
  else:
    _, f, c = q.split()
    if direction > 0:
      if f == '1':
        deq.appendleft(c)
      else:
        deq.append(c)
    else:
      if f == '1':
        deq.append(c)
      else:
        deq.appendleft(c)

if direction < 0:
  deq.reverse()
        
print(''.join(deq))
Buggy python submission (verdict: Runtime Error):
class UnionFind:
  def __init__(self, size):
    self.parents = [x for x in range(size)]
    self.sizes = [1] * size
  
  def unite(self, a, b):
    if self.find(a) == self.find(b):
      return
    
    if self.size_of(a) > self.size_of(b):
      self.sizes[self.find(a)] += self.size_of(b)
      self.parents[self.find(b)] = self.find(a)
    else:
      self.sizes[self.find(b)] += self.size_of(a)
      self.parents[self.find(a)] = self.find(b)
  
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.sizes[self.find(a)]
  
  def find(self, a):
    if a == self.parents[a]:
      return a
    else:
      self.parents[a] = self.find(self.parents[a])
      return self.parents[a]


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

u = UnionFind(N)

# 自分自身・友達・ブロック関係のいずれかの場合はフラグ立つ
relations = [1 << i for i in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  relations[a] |= 1 << b
  relations[b] |= 1 << a
  u.unite(a, b)
  
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if u.is_same(c, d):
    relations[c] |= 1 << d
    relations[d] |= 1 << c

candidates = []

for i in range(N):
  candidates.append(u.size_of(i) - bin(relations[i]).count('1'))
    
print(' '.join(str(x) for x in candidates))

Fixed submission:
from math import ceil

N = int(input());

print(ceil(N / 2))
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappushpop


N, M = map(int, input().split())
numbers = [int(n) for n in input().split()]

heapify(numbers)

for _ in range(M):
  b, c = map(int, input().split())
  for _ in range(b):
    if numbers[0] < c:
      heappushpop(numbers, c)
      
print(sum(numbers))      

Fixed submission:
from collections import Counter

N, M = map(int, input().split())
numbers = Counter(int(n) for n in input().split())

# (数, 出現回数)
q = []

for k, v in numbers.items():
  q.append((k, v))

for _ in range(M):
  b, c = map(int, input().split())
  q.append((c, b))
  
q.sort(reverse=True)

bigger = []

for k, v in q:
  if len(bigger) >= N:
    break
  for _ in range(v):
    bigger.append(k)
    if len(bigger) >= N:
      break

print(sum(bigger))
Buggy python submission (verdict: Runtime Error):
from collections import namedtuple

Edge = namedtuple('Edge', 'to cost')

N = int(input())

# index と頂点の番号を合わせたいのでサイズを N + 1 に
colors = [0] * (N + 1)
vertexes = [[] for _ in range(N + 1)]

for _ in range(N - 1):
  u, v, w = map(int, input().split())
  # 無向グラフなので双方向にリンクする
  vertexes[u].append(Edge(v, w))
  vertexes[v].append(Edge(u, w))


def dfs(id, color):
  colors[id] = color
  for edge in vertexes[id]:
    if edge.cost % 2 != 0:
      if colors[edge.to] == color:
        return False
      if colors[edge.to] == 0 and not dfs(edge.to, -color):
        return False
    elif colors[edge.to] == 0:
      dfs(edge.to, color)
  return True

if dfs(1, 1):
  for color in colors[1:]:
    print(1 if color == 1 else 0)


Fixed submission:
import sys
from collections import namedtuple


sys.setrecursionlimit(10**5)

Edge = namedtuple('Edge', 'to cost')

N = int(input())

# index と頂点の番号を合わせたいのでサイズを N + 1 に
colors = [0] * (N + 1)
vertexes = [[] for _ in range(N + 1)]

for _ in range(N - 1):
  u, v, w = map(int, input().split())
  # 無向グラフなので双方向にリンクする
  vertexes[u].append(Edge(v, w))
  vertexes[v].append(Edge(u, w))


def dfs(id, color):
  colors[id] = color
  for edge in vertexes[id]:
    if edge.cost % 2 != 0:
      if colors[edge.to] == color:
        return False
      if colors[edge.to] == 0 and not dfs(edge.to, -color):
        return False
    elif colors[edge.to] == 0:
      dfs(edge.to, color)
  return True

if dfs(1, 1):
  for color in colors[1:]:
    print(1 if color == 1 else 0)
Buggy python submission (verdict: Runtime Error):
N = int(input())

ends_with_A = 0
starts_with_B = 0
both = 0

count = 0

for _ in range(N):
  s = input()
  count += s.count('AB')
  if s.endswith('A') and s.startswith('B'):
    both += 1
  elif s.endswith('A'):
    ends_with_A += 1
  elif s.startswith('B'):
    starts_with_B += 1

if ends_with_A or starts_with_B:
  print(count + both + min(ends_with_A, starts_with_B))
else:  
  print(max(count + both + min(ends_with_A, starts_with_B) - 1), 0)
  

Fixed submission:
N = int(input())

ends_with_A = 0
starts_with_B = 0
both = 0

count = 0

for _ in range(N):
  s = input()
  count += s.count('AB')
  if s.endswith('A') and s.startswith('B'):
    both += 1
  elif s.endswith('A'):
    ends_with_A += 1
  elif s.startswith('B'):
    starts_with_B += 1

# 結合した文字が AXXXXXX or XXXXXXXB となるとき     
if ends_with_A + starts_with_B > 0:
  print(count + both + min(ends_with_A, starts_with_B))
else:  
  print(count + max(both - 1, 0) + min(ends_with_A, starts_with_B))
Buggy python submission (verdict: Runtime Error):
N, Q = map(int, input().split())
S = input()

cumulatives = [0] * (N + 1)

for i in range(N):
  # 右隣にCが来るAの数を数える
  if S[i:i + 2] == 'AC':
    cumulatives[i + 1] = cumulatives[i] + 1
  else:
    cumulatives[i + 1] = cumulatives[i]

for i in range(Q):  
  l, r = map(lambda x: int(x) - 1, input().split())  # index 合わせる
  # 右隣の文字がCでない場合は条件を満たさないので右端を1左にずらす（開区間と考える）
  print(cumulatives[r] - cumulatives[l])　　　　　　　　　　　　　　　　　　

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

cumulatives = [0] * (N + 1)

for i in range(N):
  if i == 0:
    cumulatives[1] = 0
  elif S[i - 1] == 'A' and S[i] == 'C':
    cumulatives[i + 1] = cumulatives[i] + 1
  else:
    cumulatives[i + 1] = cumulatives[i]
        
for _ in range(Q):
  l, r = map(lambda x: int(x) - 1, input().split())
  if l > 0 and S[l - 1] == 'A' and S[l] == 'C':
    # 右も閉区間なので+1
    print(cumulatives[r + 1] - cumulatives[l] - 1)
  else:
    print(cumulatives[r + 1] - cumulatives[l])
Buggy python submission (verdict: Runtime Error):
import sys
from functools import lru_cache

INF = sys.maxsize

N = int(input().strip())
h = [int(x) for x in input().split()]

@lru_cache()
def solve(i):
  if i >= N - 1:
    return 0
  return min(    
    solve(i + 1) + abs(h[i] - h[i + 1]) if i + 1 < N else INF,
    solve(i + 2) + abs(h[i] - h[i + 2]) if i + 2 < N else INF
  )
  

print(solve(0))

Fixed submission:
import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)

INF = sys.maxsize

N = int(input().strip())
h = [int(x) for x in input().split()]

@lru_cache()
def solve(i):
  if i >= N - 1:
    return 0
  return min(    
    solve(i + 1) + abs(h[i] - h[i + 1]) if i + 1 < N else INF,
    solve(i + 2) + abs(h[i] - h[i + 2]) if i + 2 < N else INF
  )
  
print(solve(0))

Buggy python submission (verdict: Runtime Error):
import sys
from functools import lru_cache

INF = sys.maxsize

N = int(input().strip())
h = [int(x) for x in input().split()]

@lru_cache(maxsize = 100000)
def solve(i):
  if i >= N - 1:
    return 0
  return min(    
    solve(i + 1) + abs(h[i] - h[i + 1]) if i + 1 < N else INF,
    solve(i + 2) + abs(h[i] - h[i + 2]) if i + 2 < N else INF
  )
  

print(solve(0))

Fixed submission:
import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)

INF = sys.maxsize

N = int(input().strip())
h = [int(x) for x in input().split()]

@lru_cache()
def solve(i):
  if i >= N - 1:
    return 0
  return min(    
    solve(i + 1) + abs(h[i] - h[i + 1]) if i + 1 < N else INF,
    solve(i + 2) + abs(h[i] - h[i + 2]) if i + 2 < N else INF
  )
  
print(solve(0))
Buggy python submission (verdict: Time Limit Exceeded):
import sys


INF = sys.maxsize

N, K = (int(x) for x in input().split())
heights = [int(x) for x in input().split()]

memo = [INF] * N

for i in range(N - 1, -1, -1):
  if i == N - 1:
    # ゴールからゴールの距離を0で初期化
    memo[i] = 0
    continue
  cost = INF
  for j in range(1, K + 1):
    # 範囲外
    if i + j >= N:
      continue
    cost = min(cost, memo[i + j] + abs(heights[i] - heights[i + j]))
  memo[i] = cost             

print(memo[0])


Fixed submission:
import sys


INF = sys.maxsize

N, K = (int(x) for x in input().split())
heights = [int(x) for x in input().split()]

memo = [INF] * N

for i in range(N - 1, -1, -1):
  if i == N - 1:
    # ゴールからゴールの距離を0で初期化
    memo[i] = 0
    continue
  cost = INF
  for j in range(1, K + 1):
    # 範囲外
    if i + j >= N:
      continue
    cost = min(cost, memo[i + j] + abs(heights[i] - heights[i + j]))
  memo[i] = cost             

print(memo[0])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 6)

N = int(input())

plans = []

for _ in range(N):
  a, b, c = map(int, input().split())
  plans.append((a, b, c))

  
@lru_cache(maxsize=None)
def max_utility_at(day, i):
  candidates = [
    (1, 2),
    (0, 2),
    (0, 1)
  ]
  if day == 0:
    return plans[0][i]
  else:    
    return max(max_utility_at(day - 1, x) + plans[day][i] for x in candidates[i])

  
print(max(max_utility_at(N - 1, x) for x in (0, 1, 2)))

Fixed submission:
N = int(input())

activities = []

for i in range(N):
  activities.append([int(x) for x in input().split()])
  
memo = [[0] * N for _ in range(3)]

for day in range(N):
  for no in range(3):
    # 1日目を初期化
    if day == 0:
      memo[no][0] = activities[0][no]
      continue
    # 同じアクティビティが連続しないように
    memo[no][day] = max(
      memo[(no + 1) % 3][day - 1], 
      memo[no - 1][day - 1]
    ) + activities[day][no]
    
print(max(memo[x][N -1] for x in range(3)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import namedtuple

Item = namedtuple('Item', 'w v')

N, W = (int(x) for x in input().split())

items = []

for _ in range(N):
  w, v = (int(x) for x in input().split())
  items.append(Item(w, v))

memo = [[0] * (W + 1) for _ in range(N)]

for i in range(N):
  for w in range(W + 1):
    if i == 0:
      # 1行目を初期化
      memo[i][w] = items[i].v if items[i].w <= w else 0
      continue
    if w < items[i].w:
      # 入らなければひとつ上の行の値をそのまま使う
      memo[i][w] = memo[i - 1][w]
      continue
    memo[i][w] = max(memo[i - 1][w], memo[i - 1][w - items[i].w] + items[i].v)

print(memo[N - 1][W])

Fixed submission:
from collections import namedtuple


Item = namedtuple('Item', 'w v')

N, W = map(int, input().split())

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))

memo = [0] * (W + 1)

for item in items:
  for w in range(W, item.w - 1, -1):
    memo[w] = max(memo[w], memo[w - item.w] + item.v)
    
print(memo[W])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import namedtuple

INF = sys.maxsize

Item = namedtuple('Item', 'w v')

N, W = map(int, input().split())

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))
  
memo = [0] + [INF] * 100000
  
for item in items:
  for v in range(100000, item.v - 1, -1):
    memo[v] = min(memo[v], memo[v - item.v] + item.w)

print(max([v for v, w in enumerate(memo) if w <= W]))

Fixed submission:
import sys
from collections import namedtuple

INF = sys.maxsize

Item = namedtuple('Item', 'w v')

N, W = map(int, input().split())

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))
  
memo = [0] + [INF] * 100000
  
for item in items:
  for v in range(100000, item.v - 1, -1):
    memo[v] = min(memo[v], memo[v - item.v] + item.w)

print(max([v for v, w in enumerate(memo) if w <= W]))