Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
h, w, m = map(int, input().split())

hcnt = [0] * w
wcnt = [0] * h
field = {}
for i in range(m):
    y, x = map(int, input().split())
    y -= 1; x -= 1
    wcnt[y] += 1
    hcnt[x] += 1
    row = field.get(y, {})
    row[x] = True
    field[y] = row
def f(y, x):
    return bool(field.get(y, {}).get(x))
# print(wcnt)
# print(hcnt)
hmax = max(hcnt)
wmax = max(wcnt)
ans = hmax + wmax - 1
for i in np.argsort(hcnt)[::-1]:
    if hcnt[i] != hmax:
        break
    for j in np.argsort(wcnt)[::-1]:
        if wcnt[j] != wmax:
            break
        if not f(j, i):
            print(ans + 1)
            __import__("sys").exit()
print(ans)


Fixed submission:
import numpy as np
h, w, m = map(int, input().split())

hcnt = [0] * w
wcnt = [0] * h
field = {}
for i in range(m):
    y, x = map(int, input().split())
    y -= 1; x -= 1
    wcnt[y] += 1
    hcnt[x] += 1
    row = field.get(y, {})
    row[x] = True
    field[y] = row
def f(y, x):
    return bool(field.get(y, {}).get(x))
# print(wcnt)
# print(hcnt)
hmax = max(hcnt)
wmax = max(wcnt)
ans = hmax + wmax - 1
harg = np.argsort(hcnt)[::-1]
warg = np.argsort(wcnt)[::-1]
for i in harg:
    if hcnt[i] != hmax:
        break
    for j in warg:
        if wcnt[j] != wmax:
            break
        if not f(j, i):
            print(ans + 1)
            __import__("sys").exit()
print(ans)
Buggy python submission (verdict: Runtime Error):
a = list(map(int, input()))
print(sum(range(1, 5 + 1)) - sum(a))

Fixed submission:
a = list(map(int, input().split()))
print(sum(range(1, 5 + 1)) - sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
n, m, q = map(int, input().split())

query = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    query.append([a - 1, b - 1, c, d])

def bit_iter(x):
    while x:
        yield x & 1
        x >>= 1


scores = []
for state in range(1 << q):
    A = [None] * n
    score = 0
    for i, v in enumerate(bit_iter(state)):
        if v:
            a, b, c, d = query[i]
            if A[a] is None:
                if A[b] is None:
                    A[a] = 1
                else:
                    A[a] = A[b] - c

            if A[a] and A[b] and A[b] - A[a] != c:
                break

            A[b] = c + A[a]
            if A[a] < 1 or A[b] > m:
                break
            score += d
    else:
        scores.append(score)
print(max(scores))


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

query = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    query.append([a - 1, b - 1, c, d])


results = []
def f(x, A, depth=0):
    if depth == n:
        # print(A, "---------" if A == [1, 3, 4] else '')
        score = 0
        for a, b, c, d in query:
            # print(A[b], A[a], A[b] - A[a], c, ":", d)
            if A[b] - A[a] == c:
                score += d
        results.append(score)
        return

    for i in range(1, x + 1):
        A[n - depth - 1] = i
        f(i, A, depth + 1)

f(m, [0] * n)
print(max(results))
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())

if n % 2: # odd
    raise Exception()
    for i in range(n // 2):
        print(i + 1, n - i)
else: # even
    a = [True] * n
    cnt = 1
    for i in range(n):
        if i + cnt >= n:
            break
        if a[i]:
            print(i + 1, i + 1 + cnt)
            a[i + cnt] = False
            cnt += 1


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

if n % 2: # odd
    for i in range(m):
        print(i + 1, n - i)
else: # even
    for i in range(m):
        if 1 + 2 * i >= n - 1 - 2 * i:
            l1 = i
            break
        m -= 1
        print(i + 1, n - i)

    for i in range(m):
        if i + 1 + l1 >= n - i - l1 - 1:
            raise Exception()
        print(i + 1 + l1, n - i - l1 - 1)
Buggy python submission (verdict: Runtime Error):
import bisect

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

graph = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = map(lambda x: int(x) - 1, input().split())
    graph[u].append(v)
    graph[v].append(u)

rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            rooted[node].append(child)
            # rooted[child].append(node)
            que.append((child, node))
            # print(child + 1, node + 1)

table = [float('inf')] * n
lis = [None] * n
def dfs(node):
    p = bisect.bisect_left(table, a[node])
    table[p], old = a[node], table[p]
    for child in rooted[node]:
        dfs(child)
    table[p] = old
    lis[node] = p + 1

dfs(0)
print(*map(str, lis), sep="\n")


Fixed submission:
import sys
import bisect
sys.setrecursionlimit(10**6)

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

graph = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = map(lambda x: int(x) - 1, input().split())
    graph[u].append(v)
    graph[v].append(u)

rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            rooted[node].append(child)
            # rooted[child].append(node)
            que.append((child, node))
            # print(child + 1, node + 1)

table = [float('inf')] * n
lis = [None] * n
def dfs(node, length=0):
    p = bisect.bisect_left(table, a[node])
    table[p], old = a[node], table[p]
    length = max(p + 1, length)
    for child in rooted[node]:
        dfs(child, length)
    table[p] = old
    lis[node] = length

dfs(0)
print(*map(str, lis), sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
]

def bfs(start, goal):
    visited = [[False] * w for _ in range(h)]
    que = deque([start + (0,)])

    max_cnt = -1
    while que:
        y, x, cnt = que.popleft()
        if 0 <= x < w and 0 <= y < h and maze[y][x] == '.' and not visited[y][x]:
            max_cnt = max(cnt, max_cnt)
            visited[y][x] = cnt + 1
            for dy, dx in directions:
                que.append((y + dy, x + dx, visited[y][x]))
    # print("\n".join([" ".join(map(str, v)) for v in visited]))
    return max_cnt

ans = 0
for sx in range(w):
    for sy in range(h):
        for gx in range(w):
            for gy in range(h):
                ans = max(ans, bfs((sy, sx), (gy, gx)))
print(ans)


Fixed submission:
from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
]

def bfs(start):

    visited = [[False] * w for _ in range(h)]
    que = deque([start + (0,)])

    max_cnt = -1
    while que:
        y, x, cnt = que.popleft()
        if 0 <= x < w and 0 <= y < h and maze[y][x] == '.' and not visited[y][x]:
            max_cnt = max(cnt, max_cnt)
            visited[y][x] = cnt + 1
            for dy, dx in directions:
                que.append((y + dy, x + dx, visited[y][x]))
    # print("\n".join([" ".join(map(str, v)) for v in visited]))
    return max_cnt

ans = 0
for sx in range(w):
    for sy in range(h):
        ans = max(ans, bfs((sy, sx)))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import itertools

n = int(input())

route = [np.array(list(map(int, input().split()))) for _ in range(n)]
results = []
for v in itertools.permutations(route, r=n):
    distance = 0
    for start, goal in zip(v[:-1], v[1:]):
        distance += np.linalg.norm(goal - start)
    results.append(distance)
print(np.mean(results))


Fixed submission:
import itertools

n = int(input())

route = [list(map(int, input().split())) for _ in range(n)]
results = []
for v in itertools.permutations(route, r=n):
    distance = 0
    for i in range(n - 1):
        start, goal = v[i], v[i + 1]
        distance += ((goal[0] - start[0]) ** 2 + (goal[1] - start[1]) ** 2) ** 0.5
    results.append(distance)
print(sum(results) / len(results))
Buggy python submission (verdict: Runtime Error):
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
print(1 / np.sum(1 / a))

Fixed submission:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
print(1 / np.sum(1 / a))
Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    # print(a, b)

nodes = [0 for _ in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    nodes[p] += x

# print(nodes)
result = [0 for _ in range(n + 1)]
def dfs(i=1, cost=nodes[1]):
    result[i] = cost
    for sub in graph[i]:
        dfs(sub, cost + nodes[sub])
dfs()
print(*result[1:])


Fixed submission:
from collections import deque
n, q = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    # print(a, b)

nodes = [0 for _ in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    nodes[p] += x

# print(nodes)
result = [0 for _ in range(n + 1)]

# que = [(1, nodes[1])]
que = deque([(1, nodes[1])])

visited = [False] * (n + 1)
while que:
    i, cost = que.popleft()
    if visited[i]:
        continue
    result[i] = cost
    visited[i] = True
    for sub in graph[i]:
        que.append((sub, cost + nodes[sub]))
print(*result[1:])
Buggy python submission (verdict: Runtime Error):
import itertools
import numpy as np
n, d = map(int, input().split())

points = [list(map(int, input().split())) for x in range(n)]

cnt = 0
for p1, p2 in itertools.combinations(points, r=2):
    d = np.linalg.norm(np.array(p1) - p2)
    if d == int(d):
        cnt += 1
print(cnt)


Fixed submission:
import itertools
import numpy as np
n, d = map(int, input().split())

points = [list(map(int, input().split())) for x in range(n)]

cnt = 0
for p1, p2 in itertools.combinations(points, r=2):
    d = np.linalg.norm(np.array(p1) - p2)
    if d == int(d):
        cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
M = 1000000007
n, k = map(int, input().split())

graph = [[] for _ in range(n)]

for i in range(n - 1):
    f, t = map(int, input().split())
    graph[f - 1].append(t - 1)
    graph[t - 1].append(f - 1)

visited = [False] * n

visited[0] = True
cnt = 0
ans = k
que = [0]
while que:
    node = que.pop()
    visited[node] = True
    node_cnt = 0
    for next_node in graph[node]:
        if not visited[next_node]:
            que.append(next_node)
            if cnt < 1:
                ans *= k - 1
                cnt += 1
                node_cnt -= 1
            else:
                ans *= (k - (2 + node_cnt))
            node_cnt += 1
print(ans % M)


Fixed submission:
M = 1000000007
n, k = map(int, input().split())

graph = [[] for _ in range(n)]

for i in range(n - 1):
    f, t = map(int, input().split())
    graph[f - 1].append(t - 1)
    graph[t - 1].append(f - 1)

visited = [False] * n

visited[0] = True
cnt = 0
ans = k
que = [0]
while que:
    node = que.pop()
    visited[node] = True
    node_cnt = 0
    for next_node in graph[node]:
        if not visited[next_node]:
            que.append(next_node)
            if cnt < 1:
                ans *= k - 1
                cnt += 1
                node_cnt -= 1
            else:
                ans *= (k - (2 + node_cnt))
                if ans > M:
                    ans %= M
            node_cnt += 1
print(ans % M)
Buggy python submission (verdict: Runtime Error):
import itertools
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if k <= (n - 1) * (n - 2) // 2:
#         return -1
# if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print(-1)


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

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print("1\n1 2" if k == 0 else -1)

Buggy python submission (verdict: Runtime Error):
import itertools
from tqdm import tqdm
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if k <= (n - 1) * (n - 2) // 2:
#         return -1
# if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print(-1)


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

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print("1\n1 2" if k == 0 else -1)

Buggy python submission (verdict: Runtime Error):
import itertools
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print(-1)


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

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print("1\n1 2" if k == 0 else -1)
Buggy python submission (verdict: Runtime Error):
import bisect
M = 1000000007

# def dfs(i):
#     if i >= n - 1:
#         return 1
#     if dp[i] is not None:
#         return dp[i]
#     if i <= maxv and a[bisect.bisect_left(a, i)] == i:
#         dp[i] = 0
#         return 0
#     r = (dfs(i + 1) + dfs(i + 2)) % M
#     dp[i] = r
#     return r

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.sort()
maxv = max(a)
# dp = [None] * n
# print(dfs(0) % M)

dp = [1] * (n + 2)
for i in range(n - 2, -1, -1):
    if i <= maxv and a[bisect.bisect_left(a, i)] == i:
        dp[i] = 0
    else:
        dp[i] = (dp[i + 1] + dp[i + 2]) % M

print(dp[0] % M)


Fixed submission:
import bisect
M = 1000000007

# def dfs(i):
#     if i >= n - 1:
#         return 1
#     if dp[i] is not None:
#         return dp[i]
#     if i <= maxv and a[bisect.bisect_left(a, i)] == i:
#         dp[i] = 0
#         return 0
#     r = (dfs(i + 1) + dfs(i + 2)) % M
#     dp[i] = r
#     return r

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.sort()
maxv = m and max(a) or -1
# dp = [None] * n
# print(dfs(0) % M)

dp = [1] * (n + 2)
dp[-1] = 0
for i in range(n - 1, -1, -1):
    if i <= maxv and a[bisect.bisect_left(a, i)] == i:
        dp[i] = 0
    else:
        dp[i] = (dp[i + 1] + dp[i + 2]) % M

print(dp[0] % M)
Buggy python submission (verdict: Runtime Error):
import numpy as np
n, k = map(int, input().split())
v = list(map(int, input().split()))

left = np.cumsum([0] + v)
right = np.cumsum([0] + v[::-1])

results = []
for backn in range(k + 1):
    at = k - backn

    t = min(n, at)
    # print('----', backn, t)
    for shift in range(t + 1):
        p = v[:t - shift] + v[n - shift:]
        # print(v[:t - shift], v[n - shift:])
        p.sort()
        value = sum(p[backn:])
        results.append(value)
print(max(max(results)), 0)


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

results = []
for a in range(n + 1):
    for b in range(min(n - a, k - a) + 1):
        p = v[:a] + v[n - b:]
        p.sort()
        for i in range(k - a - b + 1):
            results.append(sum(p[i:]))
print(max(results))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]

bc.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b, c in bc:
    b -= 1
    i = bisect.bisect_left(a, c)
    index = min(i - 1, b) + 1
    ans += index * c
    del a[:index]
print(sum(a) + ans)


Fixed submission:
import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]

bc.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b, c in bc:
    b -= 1
    i = bisect.bisect_left(a, c)
    index = min(i - 1, b) + 1
    ans += index * c
    del a[:index]
print(sum(a) + ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
graph = [[] for _ in range(n + 1)]

for i in range(n - 1):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
    graph[b].append((a, w))

que = [(1, 0)]

colors = [None] * (n + 1)
while que:
    now, color = que.pop(0)
    if colors[now] is not None:
        continue
    colors[now] = color

    for b, w in graph[now]:
        que.append((b, (color + (w & 1)) & 1))
print("\n".join(map(str, colors[1:])))


Fixed submission:
n = int(input())
graph = [[] for _ in range(n + 1)]

for i in range(n - 1):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
    graph[b].append((a, w))

que = [(1, 0)]

colors = [None] * (n + 1)
while que:
    now, color = que.pop(0)
    colors[now] = color

    for b, w in graph[now]:
        if colors[b] is not None:
            continue
        que.append((b, (color + (w & 1)) & 1))
print("\n".join(map(str, colors[1:])))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [None] * n
def dfs(depth=n - 1):
    if dp[depth] != None:
        return dp[depth]
    if depth == 0:
        dp[depth] = 0
        return 0
    if depth == 1:
        dp[depth] = dfs(depth=depth - 1) + diff(depth, 1)
        return dp[depth]
    dp[depth] = min(dfs(depth=depth - 1) + diff(depth, 1), dfs(depth=depth - 2) + diff(depth, 2))
    return dp[depth]


print(dfs())


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


def diff(now, d):
    return abs(a[now] - a[now - d])

# dp = [None] * n
# def dfs(depth=n - 1):
#     if dp[depth] != None:
#         return dp[depth]
#     if depth == 0:
#         dp[depth] = 0
#         return 0
#     if depth == 1:
#         dp[depth] = dfs(depth=depth - 1) + diff(depth, 1)
#         return dp[depth]
#     dp[depth] = min(dfs(depth=depth - 1) + diff(depth, 1), dfs(depth=depth - 2) + diff(depth, 2))
#     return dp[depth]
#
# print(dfs())

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))


def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    # dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
    dp[depth] = min(dp[depth - x] + diff(depth, x) for x in range(1, min(depth, k) + 1))
print(dp[-1])


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


def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    # dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
    dp[depth] = min(dp[depth - x] + diff(depth, x) for x in range(1, min(depth, k) + 1))
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
npa = np.array(a)


def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    m = min(depth, k)
    dp[depth] = np.min(dp[depth - m:depth] + np.abs(npa[depth] - npa[depth - m : depth]))
print(dp[-1])


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


def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    # dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
    dp[depth] = min(dp[depth - x] + diff(depth, x) for x in range(1, min(depth, k) + 1))
print(dp[-1])

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


def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    # dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
    dp[depth] = min(dp[depth - x] + diff(depth, x) for x in range(1, min(depth, k) + 1))
print(dp[-1])


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


def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    # dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
    dp[depth] = min(dp[depth - x] + diff(depth, x) for x in range(1, min(depth, k) + 1))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for x in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

# depthまでの荷物で、value以上になる重さの最小
dp = [[None] * (sum(vs) + 1) for _ in range(N)]
def dfs(value=0, depth=N - 1):
    if value <= 0:
        return 0

    if depth == -1:
        return float("inf")

    if dp[depth][value] is not None:
        return dp[depth][value]

    weight = min(dfs(value, depth - 1), dfs(value - vs[depth], depth - 1) + ws[depth])
    dp[depth][value] = weight
    return weight

for i in range(sum(vs) + 1):
    if dfs(i) > W:
        print(i - 1)
        break
else:
    print(i)


Fixed submission:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for x in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

# # depthまでの荷物で、value以上になる重さの最小
dp = [[None] * (sum(vs) + 1) for _ in range(N + 1)]
# def dfs(value=0, depth=N - 1):
#     if value <= 0:
#         return 0
#
#     if depth == -1:
#         return float("inf")
#
#     if dp[depth][value] is not None:
#         return dp[depth][value]
#
#     weight = min(dfs(value, depth - 1), dfs(value - vs[depth], depth - 1) + ws[depth])
#     dp[depth][value] = weight
#     return weight
#
# for i in range(sum(vs) + 1):
#     if dfs(i) > W:
#         print(i - 1)
#         break
# else:
#     print(i)

dp[-1] = [float("inf")] * len(dp[-1])
s = sum(vs)
for depth in range(N):
    for value in range(s + 1):
        if value - vs[depth] >= 0:
            dp[depth][value] = min(dp[depth - 1][value], dp[depth - 1][value - vs[depth]] + ws[depth])
        else:
            dp[depth][value] = min(dp[depth - 1][value], ws[depth])


import bisect
print(bisect.bisect_left(dp[N - 1], W + 1))