Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def solve():
    N, A, B = map(int, input().split())

    n_times = N // (A+B)
    amari = N % (A+B)
    cnt = 0
    if amari != 0:
        S = 'b' * A + 'r' * B
        S = S[0:amari]

        for ball in S:
            if ball == 'b':
                cnt += 1
    
    print(n_times * A + cnt)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N, A, B = map(int, input().split())

    n_times = N // (A+B)
    amari = N % (A+B)

    cnt = 0
    if A <= amari:
        cnt = A
    else:
        cnt = amari
    
    print(n_times * A + cnt)

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
def solve():
    N, A, B = map(int, input().split())
    if A + B == 0:
        print(0)
        exit(0)

    n_times = N // (A+B)
    amari = N % (A+B)
    cnt = 0
    if amari != 0:
        S = 'b' * A + 'r' * B
        S = S[:min(amari, len(S))]

        for ball in S:
            if ball == 'b':
                cnt += 1
    
    print(n_times * A + cnt)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N, A, B = map(int, input().split())

    n_times = N // (A+B)
    amari = N % (A+B)

    cnt = 0
    if A <= amari:
        cnt = A
    else:
        cnt = amari
    
    print(n_times * A + cnt)

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
def solve():
    N, A, B = map(int, input().split())
    n_times = N // (A+B)
    amari = N % (A+B)
    cnt = 0
    if amari != 0:
        S = 'b' * A + 'r' * B
        S = S[:min(amari, len(S)-1)]

        for ball in S:
            if ball == 'b':
                cnt += 1
    
    print(n_times * A + cnt)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N, A, B = map(int, input().split())

    n_times = N // (A+B)
    amari = N % (A+B)

    cnt = 0
    if A <= amari:
        cnt = A
    else:
        cnt = amari
    
    print(n_times * A + cnt)

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
def solve():
    N, A, B = map(int, input().split())
    n_times = N // (A+B)
    amari = N % (A+B)
    cnt = 0
    if amari != 0:
        S = 'b' * A + 'r' * B
        S = S[:amari]

        for ball in S:
            if ball == 'b':
                cnt += 1
    
    print(n_times * A + cnt)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N, A, B = map(int, input().split())

    n_times = N // (A+B)
    amari = N % (A+B)

    cnt = 0
    if A <= amari:
        cnt = A
    else:
        cnt = amari
    
    print(n_times * A + cnt)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, K = map(int, input().split())
    
    ans = 0
    while N > 0:
        N // K
        ans += 1
    
    print(ans)
    
if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N, K = map(int, input().split())
    
    ex = 1
    while K ** ex <= N:
        ex += 1
    print(ex)
    
if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
from statistics import mean
import math
def solve():
    N = int(input())
    X = list(map(int, input().split()))
    mn = mean(X)
    if isinstance(mn, int) or mn.is_integer():
        P = mn
        print(calc(X, P))
    else:
        ans = min(calc(X, math.floor(mn)), calc(X, math.ceil(mn)))
        print(ans)

def calc(X, P):
    retval = 0
    for x in X:
        retval += (x - P) ** 2 
    return retval
    
if __name__ == '__main__':
    solve()

Fixed submission:
import math
def solve():
    N = int(input())
    X = list(map(int, input().split()))

    mn = float('inf')
    for i in range(1, 101):
        mn = min(mn, calc(X, i))
    print(mn)


def calc(X, P):
    retval = 0
    for x in X:
        retval += (x - P) ** 2 
    return retval
    
if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def myPow(x,n,m):
  if n == 0:
    return 1
  if n % 2 == 0:
    return myPow(x * x % m, n / 2, m)
  else:
    return x * myPow(x, n - 1, m) % m

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

mod = 10**9+7 #出力の制限
N = n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n_comb = 2 ** n - 1
n_comb = myPow(2, n, mod) - 1
ans = n_comb - (cmb(n,a, mod) + cmb(n,b,mod))
ans %= mod
print(ans)

Fixed submission:
from functools import reduce 
def solve():
    mod = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    all_comb = pow(2, n, mod) - 1

    X = reduce(lambda x,y:x*y%mod, list(range(n-a+1, n+1))) 
    Y = reduce(lambda x,y:x*y%mod, list(range(1,a+1)))
    Y = pow(Y, mod-2, mod)
    a_comb = X * Y % mod

    X = reduce(lambda x,y:x*y%mod, list(range(n-b+1, n+1))) 
    Y = reduce(lambda x,y:x*y%mod, list(range(1,b+1)))
    Y = pow(Y, mod-2, mod)
    b_comb = X * Y % mod

    ans = all_comb - a_comb
    ans %= mod
    ans -= b_comb
    ans %= mod
    print(ans)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
def solve():
    N = int(input())
    d = defaultdict(int)

    for _ in range(N):
        S = input()
        d[S] += 1

    items = list(d.items())
    items.sort(key=lambda x:x[1], reverse=True)
    mx = items[0][1]
    cand = []
    for item in items:
        if item[1] == mx:
            cand.append(item[0])
        else:
            break
    
    print(*ans, sep='\n')
    
if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N = int(input())
    dict = {}

    for _ in range(N):
        S = input()
        if S in dict:
            dict[S] += 1
        else:
            dict[S] = 1
    sorted_dict = list(sorted(dict.items(), key=lambda x:x[1], reverse=True))
    mx = sorted_dict[0][1]
    cand = []
    for d in sorted_dict:
        if d[1] == mx:
            cand.append(d[0])
        else:
            break
    print(*sorted(cand), sep='\n')
    
if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    K = int(input())
    num = []
    dfs(0,0,num,N,K)
    print(len(num))

def dfs(now,cnt,lst,N,K):
    if now > N:
        return
    
    if cnt == K:
        lst.append(now)
    
    for i in range(10):
        next = now * 10 + i
        if i == 0:
            if now == 0:
                continue
            dfs(next,cnt,lst,N,K)
        else:
            dfs(next,cnt+1,lst,N,K)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N = input()
    K = int(input())
    dp = [[[0]*(K+2) for i in range(2)] for j in range(len(N)+1)]
    dp[0][False][0] = 1

    for i in range(len(N)):
        for k in range(K+1):
            dp[i+1][True][k+1] += dp[i][True][k] * 9
            dp[i+1][True][k] += dp[i][True][k]

            if int(N[i]) > 0:
                dp[i+1][True][k+1] += dp[i][False][k] * (int(N[i]) - 1)
                dp[i+1][True][k] += dp[i][False][k]
            
            if int(N[i]) > 0:
                dp[i+1][False][k+1] = dp[i][0][k]
            else:
                dp[i+1][False][k] = dp[i][0][k]
    
    print(dp[-1][False][K] + dp[-1][True][K])

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
    N, W = map(int, input().split())
    MAX_V = 100000
    MAX_N = 100
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)

    dp = [[float('inf') for i in range(MAX_V+1)] for j in range(MAX_N+1)]

    dp[0][0] = 0

    for i in range(N):
        for sum_v in range(MAX_V):
            if sum_v - v[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
            
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        
    res = 0
    for sum_v in range(MAX_V+1):
        if dp[N][sum_v] <= W:
            res = sum_v
    print(res)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    h, n = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(n)]

    mxA = 10 ** 4
    dp = [[10**15 for i in range(h+1+mxA)] for i in range(n+1)]

    for i in range(n+1):
        dp[i][0] = 0

    for i in range(n):
        for sum_dam in range(h+1+mxA):
            if sum_dam-l[i][0]>=0:
                dp[i+1][sum_dam] = min(dp[i+1][sum_dam],  \
                                dp[i][sum_dam - l[i][0]] + l[i][1],  \
                                dp[i+1][sum_dam-l[i][0]] + l[i][1])
            dp[i+1][sum_dam] = min(dp[i+1][sum_dam], dp[i][sum_dam])

    print(min(dp[-1][h:h+mxA+1]))

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import fractions
def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    div2cnt = 0
    while int(A[0]/2) % (2 ** div2cnt+1) == 0:
        div2cnt += 1

    lcmval = 0
    for i in range(1, N):
        if int(A[i]/2) % (2 ** (div2cnt+1)) == 0 or int(A[i]/2) % (2 ** div2cnt) != 0:
            print(0)
            exit(0)
        
        if i == 1:
            lcmval = lcm(A[i-1]/2, A[i]/2)
        else:
            lcmval = lcm(lcmval, A[i]/2)
    
    print(int((M-lcmval)//(lcmval* 2)+ 1))

def lcm(x, y):
    return x * y // fractions.gcd(x, y)
if __name__ == '__main__':
    solve()


Fixed submission:
import fractions
def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    div2cnt = 0
    a = A[0]
    while a % 2 == 0:
        a //= 2
        div2cnt += 1

    lcmval = A[0]//2
    for i in range(1, N):
        if A[i] % (2 ** (div2cnt+1)) == 0 or A[i] % (2 ** div2cnt) != 0:
            print(0)
            exit(0)
        
        lcmval = lcm(lcmval, A[i]//2)
        if lcmval > M:
            print(0)
            exit(0)
    
    print(int((M-lcmval)//(lcmval* 2)+ 1))

def lcm(x, y):
    return x * y // fractions.gcd(x, y)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
    X = input()
    twoDig = int(X[len(X)-2:])
    rest = int(X[:len(X)-2])

    ans = '1'
    for i in range(rest+1):
        if twoDig == 0:
            break
        for n in range(5, 0, -1):
            if twoDig - n >= 0:
                twoDig -= n
                break
    else:
        ans = '0'
    
    print(ans)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    X = input()

    if int(X) < 100:
        print('0')
        exit(0)

    twoDig = int(X[len(X)-2:])
    rest = int(X[:len(X)-2])

    ans = '1'
    for i in range(rest+1):
        if twoDig == 0:
            break
        for n in range(5, 0, -1):
            if twoDig - n >= 0:
                twoDig -= n
                break
    else:
        ans = '0'
    
    print(ans)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    S = input()

    ans = 0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                num = [i,j,k]
                idx = 0
                for digit in S:
                    digit = int(digit)
                    if digit == num[idx]:
                        idx += 1
                    if idx == 3:
                        ans += 1
                        break
    
    print(ans)

if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    N = int(input())
    S = input()

    cnt = 0
    for i in range(1000):
        target = str(i).zfill(3)
        idx = 0
        for ch in S:
            if ch == target[idx]:
                idx += 1
                if idx == 3:
                    cnt += 1
                    break
    
    print(cnt)

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    S = input()

    ans = 0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                num = [i,j,k]
                idx = 0
                for digit in S:
                    digit = int(digit)
                    if digit == num[idx]:
                        idx += 1
                    if idx == 3:
                        ans += 1
                        break
    
    print(ans)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N = int(input())
    S = input()

    cnt = 0
    for i in range(1000):
        target = str(i).zfill(3)
        idx = 0
        for ch in S:
            if ch == target[idx]:
                idx += 1
                if idx == 3:
                    cnt += 1
                    break
    
    print(cnt)

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
def solve():
    N = int(input())
    S = input()
    comb = list(itertools.combinations(list(S), 3))
    print(len(set((comb))))

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N = int(input())
    S = input()

    cnt = 0
    for i in range(1000):
        target = str(i).zfill(3)
        idx = 0
        for ch in S:
            if ch == target[idx]:
                idx += 1
                if idx == 3:
                    cnt += 1
                    break
    
    print(cnt)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import math
def solve():
    A, B, X = map(int, input().split())
    
    ans = 0
    for d in range(1, 18):
        N = (X - B*d)/A
        N = int(math.ceil(N))
        if N <= 0:
            continue
        if d == len(str(N)):
            if d >= 10:
                ans = 10**9
            else:
                ans = N
    
    print(ans)
 
if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    S = input()
    day = ["MON","TUE","WED","THU","FRI","SAT","SUN"]
    for i in range(len(day)):
        if S == "SUN":
            print(7)
            break
        elif S == day[i]:
            print(6-i)
            break
if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
    N = int(input())
    A = list(map(int,input().split()))

    sm = sum(A)
    agg = 0
    idx = 0
    mid = sm / 2
    while agg < mid:
        agg += A[idx]
        idx += 1
    
    ans = min(abs(agg-mid) / 0.5, abs(agg-A[idx]-mid)/0.5)
    
    print(int(ans))

if __name__ == '__main__':
    solve()

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

    sm = sum(A)
    agg = 0
    idx = 0
    mid = sm / 2
    shrink_cnt = sm - N
    while agg < mid and idx < N-1:
        
        agg += A[idx]
        idx += 1
    
    oneleft = agg
    oneright = sm - oneleft 
    twoleft = agg-A[idx-1]
    tworight = sm - twoleft
    ans = min(abs(oneleft-oneright), abs(twoleft-tworight))

    print(int(ans))

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
import itertools
def solve():
    N = int(input())
    primes = itertools.permutations(prime_factorize(N))

    min_sub = float('inf')
    for p in primes:
        p = [1] + list(p) + [1]
        for border in range(1, len(p)):
            a = reduce(lambda x, y: x*y, p[:border])
            b = reduce(lambda x, y: x*y, p[border:])
        
            if min_sub > a + b:
                min_sub = a + b 
    
    print(min_sub-2)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a                

if __name__ == '__main__':
    solve()


Fixed submission:
import math
def solve():
    N = int(input())
    rootN = math.sqrt(N)

    min_val = float('inf')
    for a in range(1, math.floor(rootN) + 1):
        if N % a == 0:
            b = N / a
            min_val = min(min_val, a + b - 2)
    
    print(int(min_val))

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import math

def solve():
    A, B = map(int, input().split())

    C = math.gcd(A,B) 
    

    cnt = 1
    primeNum = []
    for i in range(3, C + 1, 2):
        if A % i == 0 and B % i == 0:
            if isPrime(i, primeNum):
                primeNum.append(i)
                cnt += 1

    if A % 2 == 0 and B % 2 == 0:
        cnt += 1

    if A == B:
        cnt += 1
    
    print(cnt)
        

def isPrime(num, primeNum):
    for n in primeNum:
        if n > math.sqrt(num):
            break 
        if num % n == 0:
            return False
        
    return True


if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    A, B = map(int, input().split())

    primeFactorA = prime_factorize(A)
    primeFactorB = prime_factorize(B)

    commonFactor = [1]
    for f in primeFactorB:
        if f in primeFactorA:
            commonFactor.append(f)
    
    print(len(commonFactor))


def prime_factorize(num):
    a = set() 
    while num % 2 == 0:
        a.add(2)
        num //= 2
    
    f = 3
    while f * f <= num:
        if num % f == 0:
            a.add(f)
            num //= f
        else:
            f += 2
    if num != 1:
        a.add(num)
    
    return a

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    A, B = map(int, input().split())

    C = max(A, B) // 2

    cnt = 1
    primeNum = []
    for i in range(3, C + 1, 2):
        if A % i == 0 and B % i == 0:
            if isPrime(i, primeNum):
                primeNum.append(i)
                cnt += 1

    if A % 2 == 0 and B % 2 == 0:
        cnt += 1
    
    print(cnt)
        

def isPrime(num, primeNum):
    for n in primeNum:
        if num % n == 0:
            return False
        
    
    return True


if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    A, B = map(int, input().split())

    primeFactorA = prime_factorize(A)
    primeFactorB = prime_factorize(B)

    commonFactor = [1]
    for f in primeFactorB:
        if f in primeFactorA:
            commonFactor.append(f)
    
    print(len(commonFactor))


def prime_factorize(num):
    a = set() 
    while num % 2 == 0:
        a.add(2)
        num //= 2
    
    f = 3
    while f * f <= num:
        if num % f == 0:
            a.add(f)
            num //= f
        else:
            f += 2
    if num != 1:
        a.add(num)
    
    return a

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
def func():
    N = int(input())
    serial = list(range(1, N + 1))

    print(sum(serial)-N)


if __name__ == '__main__':
    func()


Fixed submission:
def func():
    N = int(input())
    sum = 0
    for i in range(1, N + 1):
        sum += i

    print(sum-N)


if __name__ == '__main__':
    func()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
def solve():
    N = int(input())
    G = defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        G[u].append((v,w))
        G[v].append((u,w))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 != 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()

Fixed submission:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        G[u].append((v,w))
        G[v].append((u,w))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 != 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
def solve():
    N = int(input())
    G = defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        G[u].append((v,w))
        G[v].append((u,w))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 == 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()

Fixed submission:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        G[u].append((v,w))
        G[v].append((u,w))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 != 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, W = map(int, input().split())
    MAX_V = 100100
    MAX_N = 110
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)

    dp = [[float('inf') for i in range(MAX_V+1)] for j in range(MAX_N+1)]

    dp[0][0] = 0

    for i in range(N):
        for sum_v in range(MAX_V):
            if sum_v - v[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
            
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        
    res = 0
    for sum_v in range(MAX_V+1):
        if dp[N][sum_v] <= W:
            res = sum_v
    print(res)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    n, w = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(n)]

    lim = n * 10 ** 3 + 1
    dp = [[10**15 for i in range(lim)] for i in range(n+1)]

    for i in range(n+1):
        dp[i][0] = 0

    for i in range(n):
        for sum_v in range(lim):
            if sum_v-l[i][1]>=0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - l[i][1]] + l[i][0])
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

    ans = 0
    for sum_v in range(lim):
        if dp[n][sum_v] <= w:
            ans = sum_v

    print(ans)

if __name__ == '__main__':
    solve()