Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
A = [deque([int(i)-1 for i in input().split()]) for _ in range(N)]

def solve() :
    q = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        done = [False] * N
        schedule = []
        for i in q :
            j = A[i][0]
            if done[i] or done[j]:
                continue
                
            if i == A[j][0] :
                schedule.append(i)
                schedule.append(j)
                done[i] = done[j] = True
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print(solve())

Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
A = [deque([int(i)-1 for i in input().split()]) for _ in range(N)]

def solve() :
    q = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        schedule = set()
        for i in q :
            j = A[i][0]
            if i in schedule or j in schedule :
                continue
                
            if i == A[j][0] :
                schedule.add(i)
                schedule.add(j)
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

p = int(input())
a = [int(i) for i in input().split()]

ret = [0] * p
fac = [1]
inv = [1]
power = [0] * p
for i in range(1, p) :
    fac.append(fac[-1] * i % p)
    inv.append(pow(fac[-1], p - 2, p))

for i in range(p) :
    if a[i] == 0 :
        continue
    ret[0] += 1
    for j in range(p) :
        ret[j] += -fac[p-1]*inv[p-1-j]*inv[j]*pow(-i, p-1-j, p)%p
        ret[j] %= p

print(' '.join(map(str, ret)))

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

p = int(input())
a = [int(i) for i in input().split()]

ret = [0] * p
fac = [1]
inv = [1]
for i in range(1, p) :
    fac.append(fac[-1] * i % p)
    inv.append(pow(fac[-1], p - 2, p))

for i in range(p) :
    if a[i] == 0 :
        continue
    ret[0] += 1
    power = 1
    for j in range(p-1, -1, -1) :
        ret[j] += -fac[p-1]*inv[p-1-j]*inv[j]*power%p
        ret[j] %= p
        power *= -i
        power %= p
print(' '.join(map(str, ret)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

N = int(input())
a = [0]+[int(i) for i in input().split()]
ret = [0] * (N+1)

def rec(i) :
    if i == N + 1 :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s ^= ret[j]
    ret[i] = s^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))


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

N = int(input())
a = [0]+[int(i) for i in input().split()]
ret = [0] * (N+1)

def rec(i) :
    if i == N + 1 :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s ^= ret[j]
    ret[i] = s^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**5)

N = int(input())
a = [0]+[int(i) for i in input().split()]
ret = [0] * (N+1)

def rec(i) :
    if i == N + 1 :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s += ret[j]
    ret[i] = (s%2)^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))

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

N = int(input())
a = [0]+[int(i) for i in input().split()]
ret = [0] * (N+1)

def rec(i) :
    if i == N + 1 :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s ^= ret[j]
    ret[i] = s^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))

Buggy python submission (verdict: Runtime Error):
N = int(input())
a = [0]+[int(i) for i in input().split()]
ret = [0] * (N+1)

def rec(i) :
    if i == N :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s += ret[j]
    ret[i] = s^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))

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

N = int(input())
a = [0]+[int(i) for i in input().split()]
ret = [0] * (N+1)

def rec(i) :
    if i == N + 1 :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s ^= ret[j]
    ret[i] = s^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]

from bisect import bisect_left
	
def LIS(L) :
    step = 0
    x = 0
    while True :
        for i in range(x, N) :
            if L[i] >= 0 :
                break
        else :
            break
            
        lis = [L[i]]
        pos = [i]
        x = i
        for p in range(i+1, N) :
            a = L[p]
            if a > lis[-1] :
                lis.append(a)
                pos.append(p)
            elif a >= 0 :
                s = bisect_left(lis, a)
                if lis[s] != a :
                    lis[s] = a
                    pos[s] = p
        # print(pos)
        for p in pos :
            L[p] = -1
        # print(L)
        step += 1
    return step

print(LIS(A))

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

from bisect import bisect_right
	
def LIS(L) :   
    lis = [L[0]]
    for a in L[1:] :
        if a >= lis[-1] :
            lis.append(a)
        else :
            s = bisect_right(lis, a)
            lis[s] = a
    return len(lis)

print(LIS(A[::-1]))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

if M % 2 == 0 :
    vec = [[] for _ in range(N)]
    for _ in range(M) :
        A, B = map(int, input().split())
        vec[A-1].append(B-1)
        vec[B-1].append(A-1)

    visited = [False] * N
    CD = [[] for _ in range(N)]

    def dfs(cur, pre) :
        for nex in vec[cur] :
            if nex == pre :
                continue
            
            if not visited[nex] :
                visited[nex] = True
                dfs(nex, cur)
            elif not cur in CD[nex] :
                CD[cur].append(nex)
        
        if pre != -1 :
            if len(CD[cur]) % 2 == 0 :
                CD[pre].append(cur)
            else :
                CD[cur].append(pre)

    visited[0] = True            
    dfs(0, -1)

    for i in range(N) :
        for j in CD[i] :
            print(i + 1, j + 1)
else :
    print(-1)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

if M % 2 == 0 :
    vec = [[] for _ in range(N)]
    for _ in range(M) :
        A, B = map(int, input().split())
        vec[A-1].append(B-1)
        vec[B-1].append(A-1)

    visited = [False] * N
    CD = [[] for _ in range(N)]

    def dfs(cur, pre) :
        for nex in vec[cur] :
            if nex == pre :
                continue
            
            if not visited[nex] :
                visited[nex] = True
                dfs(nex, cur)
            elif not cur in CD[nex] :
                CD[cur].append(nex)
        
        if pre != -1 :
            if len(CD[cur]) % 2 == 0 :
                CD[pre].append(cur)
            else :
                CD[cur].append(pre)

    visited[0] = True            
    dfs(0, -1)

    for i in range(N) :
        for j in CD[i] :
            print(i + 1, j + 1)
else :
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]


def knapzap(N, A, B) :
    dp = [0] * (N + 1)
    n_ = 0
    A_, B_ = [], []
    for a, b in zip(A, B) :
        if a < b :
            A_.append(a)
            B_.append(b)
            n_ += 1

    for n in range(1, N + 1) :
        dp[n] = max([dp[n-1] + 1] + [dp[n-A_[i]] + B_[i] if n - A_[i] >= 0  else 0 for i in range(n_)])

    return dp[N]

M = knapzap(N, A, B)
ret = knapzap(M, B, A)
print(ret)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

def knapzap(N, A, B) :
    dp = [0] * (N + 1)

    for n in range(1, N + 1) :
        dp[n] = max(
            dp[n-1] + 1,
            dp[n-A[0]] + B[0] if n - A[0] >= 0 else 0,
            dp[n-A[1]] + B[1] if n - A[1] >= 0 else 0,
            dp[n-A[2]] + B[2] if n - A[2] >= 0 else 0
        )

    return dp[N]

M = knapzap(N, A, B)
ret = knapzap(M, B, A)
print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

def search1(n) :
    ret = 0
    for g in range(n // A[0] + 1) :
        n -= g*A[0]
        for s in range(n // A[1] + 1) :
            n -= s*A[1]
            for b in range(n // A[2] + 1) :
                n -= b*A[2]
                ret = max(ret, n + g*B[0]+s*B[1]+b*B[2])
                n += b*A[2]
            n += s*A[1]
        n += g*A[0]

    return ret

def search2(n) :
    ret = 0
    for g in range(n // B[0] + 1) :
        n -= g*B[0]
        for s in range(n // B[1] + 1) :
            n -= s*B[1]
            for b in range(n // B[2] + 1) :
                n -= b*B[2]
                ret = max(ret, n + g*A[0]+s*A[1]+b*A[2])
                n += b*B[2]
            n += s*B[1]
        n += g*B[0]

    return ret

M = search1(N)
ret = search2(M)
print(ret)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

def knapzap(N, A, B) :
    dp = [0] * (N + 1)

    for n in range(1, N + 1) :
        dp[n] = max(
            dp[n-1] + 1,
            dp[n-A[0]] + B[0] if n - A[0] >= 0 else 0,
            dp[n-A[1]] + B[1] if n - A[1] >= 0 else 0,
            dp[n-A[2]] + B[2] if n - A[2] >= 0 else 0
        )

    return dp[N]

M = knapzap(N, A, B)
ret = knapzap(M, B, A)
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
L = input()
MOD = 10 ** 9 + 7
N = len(L)

fact = [0] * (N + 1)
inv = [0] * (N + 1)
fact[0] = 1
inv[0] = pow(1, MOD - 2, MOD)

for i in range(1, N + 1) :
    fact[i] = (fact[i-1] * i) % MOD
    inv[i] = pow(fact[i], MOD - 2, MOD)

mem = [[-1] * (N + 1) for _ in range(N + 1)]

def comb(n, r) :
    if n < r or n < 0 or r < 0 :
        return 0
    if mem[n][r] >= 0 :
        return mem[n][r]
    else :
        mem[n][r] = (fact[n] * inv[n-r] * inv[r]) % MOD
        return mem[n][r]

ret = 0
n1 = [0] * (N + 1)

sum = 0
for k, v in enumerate(L) :
    if v == '1' :
        for i in range(N-k) :
            n1[sum+i] += comb(N-k-1, i)
        sum += 1

n1[L.count('1')] += 1
   
for i, n in enumerate(n1) :
    ret += n * pow(2, i, MOD)
    ret %= MOD
    
print(ret)

Fixed submission:
L = input()
MOD = 10 ** 9 + 7
N = len(L)

s = 0
ret = 0
for k, v in enumerate(L) :
    if v == '1' :
        ret += pow(2, s, MOD) * pow(3, N-k-1, MOD)
        ret %= MOD
        s += 1

ret += pow(2, s, MOD)

print(ret % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
L = input()
MOD = 10 ** 9 + 7
N = len(L)

fact = [0] * (N + 1)
inv = [0] * (N + 1)
fact[0] = 1
inv[0] = pow(1, MOD - 2, MOD)

for i in range(1, N + 1) :
    fact[i] = (fact[i-1] * i) % MOD
    inv[i] = pow(fact[i], MOD - 2, MOD)

def comb(n, r) :
    if n < r or n < 0 or r < 0 :
        return 0
    return (fact[n] * inv[n-r] * inv[r]) % MOD

ret = 0
n1 = [0] * (N + 1)

sum = 0
for k, v in enumerate(L) :
    if v == '1' :
        for i in range(N-k) :
            n1[sum+i] += comb(N-k-1, i)
        sum += 1

n1[L.count('1')] += 1
   
for i, n in enumerate(n1) :
    ret += n * pow(2, i, MOD)
    ret %= MOD
    
print(ret)

Fixed submission:
L = input()
MOD = 10 ** 9 + 7
N = len(L)

s = 0
ret = 0
for k, v in enumerate(L) :
    if v == '1' :
        ret += pow(2, s, MOD) * pow(3, N-k-1, MOD)
        ret %= MOD
        s += 1

ret += pow(2, s, MOD)

print(ret % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
L = input()
MOD = 10 ** 9 + 7
N = len(L)

fact = [0] * (2 * N)
inv = [0] * (2 * N)
fact[0] = 1
inv[0] = pow(1, MOD - 2, MOD)

for i in range(1, 2 * N) :
    fact[i] = (fact[i-1] * i) % MOD
    inv[i] = pow(fact[i], MOD - 2, MOD)

def comb(n, r) :
    if n < r or n < 0 or r < 0 :
        return 0
    return (fact[n] * inv[n-r] * inv[r]) % MOD

ret = 0
n1 = [0] * (N + 1)

sum = 0
for k, v in enumerate(L) :
    if v == '1' :
        for i in range(N-k) :
            n1[sum+i] += comb(N-k-1, i)
        sum += 1

n1[L.count('1')] += 1
   
for i, n in enumerate(n1) :
    ret += n * pow(2, i, MOD)
    ret %= MOD
    
print(ret)

Fixed submission:
L = input()
MOD = 10 ** 9 + 7
N = len(L)

s = 0
ret = 0
for k, v in enumerate(L) :
    if v == '1' :
        ret += pow(2, s, MOD) * pow(3, N-k-1, MOD)
        ret %= MOD
        s += 1

ret += pow(2, s, MOD)

print(ret % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
L, A, B, M = map(int, input().split())

s = [A + B * i for i in range(L)]

ret = 0
for i in range(L) :
    ret = int(str(ret) + str(s[i])) % M

print(ret)

Fixed submission:
L, A, B, M = map(int, input().split())

def mat_pow(x, n) :
    y = [[0] * 3 for _ in range(3)]
        
    for i in range(3) :
        y[i][i] = 1
        
    while n > 0 :
        if n & 1 :
            y = mat_mul(x, y)
        x = mat_mul(x, x)
        n >>= 1
        
    return y
    
def mat_mul(a, b) :
    I, J, K = len(a), len(b[0]), len(b)
    c = [[0] * J for _ in range(I)]
    for i in range(I) :
        for j in range(J) :
            for k in range(K) :
                c[i][j] += a[i][k] * b[k][j]
            c[i][j] %= M
    return c

n0 = -(-(10 ** 0 - A) // B)
n1 = -(-(10 ** 1 - A) // B)

ret = [[0], [A], [1]]

for d in range(1, 19) :
    mat = [[10**d, 1, 0], [0, 1, B], [0, 0, 1]]
    if n0 < 0 and 0 < n1 :
        n0 = 0
        
    if 0 <= n0 < n1 :
        ret = mat_mul(mat_pow(mat, n1 - n0), ret)
    n0, n1 = n1, min(-(-(10 ** (d + 1) - A) // B), L)

print(ret[0][0])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
s = [int(i) for i in input().split()]

ret = 0
for i in range(2, N - 1) :
    for j in range(1, i) :
        if (i % (i - j) == 0 and 2 * i < N) or (N - 1 - i) % (i - j) != 0 :
            continue
        
        ret = max(ret, sum(s[i::i-j]) + sum(s[i-j:-j-1:i-j]))

print(max(ret, 0))

Fixed submission:
N = int(input())
s = [int(i) for i in input().split()]

ret = 0
for c in range(1, N) :
    k = 1
    tmp = 0
    flag = (N - 1) % c == 0
    while c * k < N - 1 :
        l = c * k
        r = N - 1 - l

        if (flag and r <= l) or r <= c:
            break

        tmp += s[l] + s[r]
        ret = max(ret, tmp)
        k += 1

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, r) :
    if n - r < 0 or r < 0 :
        return 0
    
    r = min(n-r, r)

    a, b = 1, 1
    for i in range(r) :
        a *= n - i
        b *= i + 1

    return a // b

res = 0

for i in range(1, N + 1) :
    for j in range(1, M + 1) :
        if i > 1 and j > 1 :
            res += 2 * (N + 1 - i) * (M + 1 - j) * (i + j - 2)
        else :
            res += (N + 1 - i) * (M + 1 - j) * (i + j - 2)

res *= comb(N * M - 2, K - 2)

print(res % MOD)

Fixed submission:
N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

def pow(x, n) :
    y = 1
    while n > 0 :
        if n & 1 :
            y = (y * x) % MOD
        x = (x * x) % MOD
        n >>= 1

    return y

def comb(n, r) :
    if n < r or n < 0 :
        return 0

    factorial = [0] * (n + 1)
    factorial[0] = 1

    for i in range(1, n + 1) :
        factorial[i] = (factorial[i-1] * i) % MOD

    return (factorial[n] * pow(factorial[n-r], MOD - 2) * pow(factorial[r], MOD - 2)) % MOD

res = 0

for i in range(N) :
    for j in range(M) :
        if i > 0 and j > 0 :
            res += 2 * (N - i) * (M - j) * (i + j)
        else :
            res += (N - i) * (M - j) * (i + j)

res *= comb(N * M - 2, K - 2)

print(res % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, r) :
    if n - r < 0 or r < 0 :
        return 0
    
    r = min(n-r, r)

    a, b = 1, 1
    for i in range(r) :
        a *= (n - i) % MOD
        b *= (i + 1) % MOD

    return (a // b) % MOD

res = 0

for i in range(1, N + 1) :
    for j in range(1, M + 1) :
        if i > 1 and j > 1 :
            res += 2 * (N + 1 - i) * (M + 1 - j) * (i + j - 2)
        else :
            res += (N + 1 - i) * (M + 1 - j) * (i + j - 2)

res *= comb(N * M - 2, K - 2)

print(res % MOD)

Fixed submission:
N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

def pow(x, n) :
    y = 1
    while n > 0 :
        if n & 1 :
            y = (y * x) % MOD
        x = (x * x) % MOD
        n >>= 1

    return y

def comb(n, r) :
    if n < r or n < 0 :
        return 0

    factorial = [0] * (n + 1)
    factorial[0] = 1

    for i in range(1, n + 1) :
        factorial[i] = (factorial[i-1] * i) % MOD

    return (factorial[n] * pow(factorial[n-r], MOD - 2) * pow(factorial[r], MOD - 2)) % MOD

res = 0

for i in range(N) :
    for j in range(M) :
        if i > 0 and j > 0 :
            res += 2 * (N - i) * (M - j) * (i + j)
        else :
            res += (N - i) * (M - j) * (i + j)

res *= comb(N * M - 2, K - 2)

print(res % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

uvw= [[int(i) for i in input().split()] for _ in range(N-1)]

def dfs() :
	paint = [-1] * (N + 1)
	
	queue = [1]
	paint[1] = 1

	while queue :
		current = queue.pop(0)

		for u, v, w in uvw :
			if v == current :
				u, v = v, u

			if u == current and paint[v] == -1 :
				queue.append(v)
				paint[v] = (paint[u] + w) % 2

	return paint[1:]

for i in dfs() :
	print(i)

Fixed submission:
N = int(input())

uvw= [[int(i) for i in input().split()] for _ in range(N-1)]

path = [[] for _ in range(N+1)]

for u, v, w in uvw :
    path[u].append((v, w))
    path[v].append((u, w))

paint = [0] * (N + 1)

queue = [1]
visited = [False] * (N + 1)

while queue :
    current = queue.pop(0)
    w = paint[current]

    for destination, w_ in path[current] :
        if not visited[destination] :
            paint[destination] = (w + w_) & 1
            queue.append(destination)
            visited[destination] = True

for i in paint[1:] :
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N, M = map(int, input().split())
v = [[] for _ in range(N)]
p = [True] * N
for _ in range(N + M - 1) :
    A, B = map(int, input().split())
    v[A-1].append(B-1)
    p[B-1] = False
    
s = p.index(True)
dist = [0] * N
par = [-1] * N

q = deque([s])
while q :
    cur = q.popleft()
    for nex in v[cur] :
        if dist[cur] + 1 > dist[nex] :
            dist[nex] = dist[cur] + 1
            par[nex] = cur
            q.append((nex))

for i in range(N) :
    print(par[i] + 1)

Fixed submission:
N, M = map(int, input().split())
v = [[] for _ in range(N)]
u = [[] for _ in range(N)]
for _ in range(N + M - 1) :
    A, B = map(int, input().split())
    v[A-1].append(B-1)
    u[B-1].append(A-1)

for i in range(N) :
    if len(u[i]) == 0 :
        s = i
        break
        
dist = [0] * N
par = [-1] * N
cnt = [0] * N

par[s] = -1
q = [s]
while q :
    cur = q.pop()
    cnt[cur] += 1
    if cur != s and cnt[cur] != len(u[cur]) :
        continue
        
    for nex in v[cur] :
        if dist[cur] + 1 > dist[nex] :
            dist[nex] = dist[cur] + 1
            par[nex] = cur
            q.append((nex))

for i in range(N) :
    print(par[i] + 1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000)

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
wv.sort()

mem = dict()

def knapsack(i, w) :
    if i == N :
        return 0
    
    if (i, w) in mem :
        return mem[(i, w)]
    
    if w + wv[i][0] <= W :
        mem[(i, w)] = max(knapsack(i+1, w+wv[i][0])+wv[i][1], knapsack(i+1, w))
        return mem[(i, w)]
    else :
        return 0
        
print(knapsack(0, 0))

Fixed submission:
N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
V = max([wv[i][1] for i in range(N)]) * N

dp = [[float('inf')] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N) :
    for j in range(V+1) :
        if j >= wv[i][1] :
            dp[i+1][j] = min(dp[i][j-wv[i][1]] + wv[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]

for i in range(V, -1, -1) :
    if dp[N][i] <= W :
        print(i)
        break

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000)

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
wv.sort()

def knapsack(i, w) :
    if i == N :
        return 0
        
    if w + wv[i][0] <= W :
        return max(knapsack(i+1, w+wv[i][0])+wv[i][1], knapsack(i+1, w))
    else :
        return 0
        
print(knapsack(0, 0))

Fixed submission:
N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
V = max([wv[i][1] for i in range(N)]) * N

dp = [[float('inf')] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N) :
    for j in range(V+1) :
        if j >= wv[i][1] :
            dp[i+1][j] = min(dp[i][j-wv[i][1]] + wv[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]

for i in range(V, -1, -1) :
    if dp[N][i] <= W :
        print(i)
        break

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000)

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

def knapsack(i, w) :
    if i == N :
        return 0
        
    if w + wv[i][0] <= W :
        return max(knapsack(i+1, w+wv[i][0])+wv[i][1], knapsack(i+1, w))
    else :
        return knapsack(i+1, w)
        
print(knapsack(0, 0))

Fixed submission:
N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
V = max([wv[i][1] for i in range(N)]) * N

dp = [[float('inf')] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N) :
    for j in range(V+1) :
        if j >= wv[i][1] :
            dp[i+1][j] = min(dp[i][j-wv[i][1]] + wv[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]

for i in range(V, -1, -1) :
    if dp[N][i] <= W :
        print(i)
        break