Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint
import heapq

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)


# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

def dfs(n):
    if n in to:
        return
    else:
        to.add(n)
        for a, b, c in edges:
            if a == n:
                dfs(b)


def dfs2(n):
    if n in ot:
        return
    else:
        ot.add(n)
        for a, b, c in edges:
            if b == n:
                dfs2(a)


N, M, P = [int(x) for x in input().split()]
edges = []
# 1から行けるノード
to = set()
# N-1に到達できるノード
ot = set()
for _ in range(M):
    a, b, c = [int(x) for x in input().split()]
    a, b, c = a - 1, b - 1, c - P
    edges.append((a, b, -c))

dfs(0)
dfs2(N - 1)

W = [INF] * N
W[0] = 0
for cnt in range(N + 1):
    isShusoku = True
    for a, b, c in edges:
        if b in to and b in ot:
            if W[b] > W[a] + c:
                W[b] = W[a] + c
                isShusoku = False

if isShusoku == True:
    print(max(0,-W[N - 1]))
else:
    print(-1)
pass


Fixed submission:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint
import heapq

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)


# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

def dfs(n):
    if n in to:
        return
    else:
        to.add(n)
        for a, b, c in edges:
            if a == n:
                dfs(b)


def dfs2(n):
    if n in ot:
        return
    else:
        ot.add(n)
        for a, b, c in edges:
            if b == n:
                dfs2(a)


N, M, P = [int(x) for x in input().split()]
edges = []
# 1から行けるノード
to = set()
# N-1に到達できるノード
ot = set()
for _ in range(M):
    a, b, c = [int(x) for x in input().split()]
    a, b, c = a - 1, b - 1, c - P
    edges.append((a, b, -c))

dfs(0)
dfs2(N - 1)

W = [INF] * N
W[0] = 0
for cnt in range(N + 1):
    isShusoku = True
    for a, b, c in edges:
        if b in to and b in ot:
            if W[b] > W[a] + c:
                W[b] = W[a] + c
                isShusoku = False

if isShusoku == True:
    print(max(0,-W[N - 1]))
else:
    print(-1)
pass
Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))


N = int(input())
A = [int(x) for x in input().split()]
A = [0] + A

R = []

dl = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    cnt = 1
    while i * cnt <= N:
        dl[i][i * cnt] = 1
        cnt += 1

for i in range(N, 0, -1):
    if A[i] == 1:
        R.append(i)
        for j in range(i, 0, -1):
            A[j] = (A[j] + 1) % 2

print(len(R))
print(" ".join([str(i) for i in R]))

# print(R)

Fixed submission:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)


# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

def divisor_list(n):
    ret = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            ret.add(i)
            ret.add(n // i)
        i += 1
    return ret


N = int(input())
tmp = [int(x) for x in input().split()]
A = [-999]
for a in tmp:
    A.append(a)

B = []

for i in range(N, 0, -1):
    # print(i)
    if A[i] == 1:
        B.append(str(i))
        DL = divisor_list(i)
        for j in DL:
            A[j] = (A[j] + 1) % 2

print(len(B))
print(" ".join(B))

pass
Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

import heapq

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

B = []

for a in A:
    i = 0
    while i < len(B) and B[i] >= a:
        i += 1

    if i != len(B):
        B[i] = a
    else:
        B.append(a)

print(len(B))

pass


Fixed submission:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

import heapq

N = int(input())
A = []
for _ in range(N):
    A.append(-int(input()))

B = []

for a in A:
    i = bisect.bisect_right(B, a)
    if i != len(B):
        B[i] = a
    else:
        B.append(a)

# print(B)
print(len(B))

pass
Buggy python submission (verdict: Time Limit Exceeded):
import sys

# from collections import Counter, deque, defaultdict
# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N = int(input())
# XY = set()
XY = []
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    # XY.add((x,y))
    XY.append((x, y))

XY.sort()
ans = float("INF")
for i in range(N):
    for j in range(N):
        if i == j:
            continue

        p = XY[i][0] - XY[j][0]
        q = XY[i][1] - XY[j][1]

        T = [0] * N
        for k in range(N):
            if T[k] != 0:
                continue
            T[k] = 1
            curXY = (XY[k][0], XY[k][1])

            for l in range(N):
                if (XY[l][0], XY[l][1]) == ((curXY[0] - p, curXY[1] - q)):
                    T[l] = 2
                    curXY = XY[l]

        # ans = min(T.count(1), ans)
        if ans > T.count(1):
            ans = T.count(1)
            ansP, ansQ = p, q
            # print("ans,p,q = {},{},{}".format(ans, p, q))

if N == 1:
    ans = 1

print(ans)


Fixed submission:
import sys

# from collections import Counter, deque, defaultdict
# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N = int(input())
# XY = set()
XY = []
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    # XY.add((x,y))
    XY.append((x, y))

XY.sort()
ans = float("INF")
for i in range(N):
    for j in range(N):
        if i == j:
            continue

        p = XY[i][0] - XY[j][0]
        q = XY[i][1] - XY[j][1]

        T = [0] * N
        for k in range(N):
            if T[k] != 0:
                continue
            T[k] = 1
            curXY = (XY[k][0], XY[k][1])

            for l in range(N):
                if (XY[l][0], XY[l][1]) == ((curXY[0] - p, curXY[1] - q)):
                    T[l] = 2
                    curXY = XY[l]

        # ans = min(T.count(1), ans)
        if ans > T.count(1):
            ans = T.count(1)
            ansP, ansQ = p, q
            # print("ans,p,q = {},{},{}".format(ans, p, q))

if N == 1:
    ans = 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

# from collections import Counter, deque, defaultdict
# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

H, W = [int(x) for x in input().split()]
S = []
for h in range(H):
    S.append(input())

Th = [[0] * W for _ in range(H)]
Tw = [[0] * W for _ in range(H)]

for h in range(H):
    cnt = 0
    st = 0
    for w in range(W):
        if S[h][w] == "#":
            for i in range(st, w):
                Tw[h][i] = cnt
            st = w + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, W):
        Tw[h][i] = cnt

for w in range(W):
    cnt = 0
    st = 0
    for h in range(H):
        if S[h][w] == "#":
            for i in range(st, h):
                Th[i][w] = cnt
            st = h + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, H):
        Th[i][w] = cnt

ALL = []
for w in range(W):
    for h in range(H):
        ALL.append(Tw[h][w] + Th[h][w])

print(max(ALL) - 1)


Fixed submission:
import sys

# from collections import Counter, deque, defaultdict
# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

H, W = [int(x) for x in input().split()]
S = []
for h in range(H):
    S.append(input())

Th = [[0] * W for _ in range(H)]
Tw = [[0] * W for _ in range(H)]

for h in range(H):
    cnt = 0
    st = 0
    for w in range(W):
        if S[h][w] == "#":
            for i in range(st, w):
                Tw[h][i] = cnt
            st = w + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, W):
        Tw[h][i] = cnt

for w in range(W):
    cnt = 0
    st = 0
    for h in range(H):
        if S[h][w] == "#":
            for i in range(st, h):
                Th[i][w] = cnt
            st = h + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, H):
        Th[i][w] = cnt

ALL = []
for w in range(W):
    for h in range(H):
        ALL.append(Tw[h][w] + Th[h][w])

print(max(ALL) - 1)
Buggy python submission (verdict: Runtime Error):
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

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

import itertools

RV = list(itertools.accumulate(V))

# 左から最大でl個とる
# for l in range(K + 1):
#     # 右からは最大でk-l個
#     for r in range(K + 1 - l):
#         print("l:{}, r:{}".format(l, r))


# heapq.heappush(Q,)
import heapq

from collections import defaultdict


def f(k):
    ret = -99999999999999999999999
    dd = defaultdict(lambda: 0)
    s = 0
    for i in range(k):
        s += V[-k + i]
        dd[V[-k + i]] += 1

    ret = max(ret, s - neg(dd, K - k))

    for i in range(k):
        rm = V[-k + i]
        ad = V[-k + i + k]
        dd[rm] -= 1
        dd[ad] += 1
        s -= rm
        s += ad
        ret = max(ret, s - neg(dd, K - k))
        # print(ret)

    return ret


def neg(d, n):
    L = sorted(d.items())
    ret = 0

    for l in L:
        v, cnt = l[0], l[1]
        if n <= 0 or v >= 0:
            break

        if n >= cnt:
            ret += (v * cnt)
        else:
            ret += (v * n)
        n -= cnt
    return ret


ans = 0
for i in range(1, K + 1):
    ans = max(ans, f(i))
print(ans)


Fixed submission:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

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

ans = 0
# 左からl個(0..K)
for l in range(K + 1):
    # 右からはr個(0..K-l)
    for r in range(K - l + 1):
        # N個よりは取れない
        if l + r > N:
            continue
        # 残りの操作数
        d = max(0, K - (l + r))

        # 合計値
        s = sum(V[:l]) + sum(V[N - r:])
        # 手元のマイナス
        neg = filter(lambda x: x < 0, V[:l] + V[N - r:])
        neg = list(neg)
        neg.sort()
        for i in range(d):
            if i < len(neg):
                s -= neg[i]

        # print(s)
        ans = max(ans,s)

print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = [int(x) for x in input().split()]

# Union Find
# N = 100
PARENT = list(range(N))

used = set()


def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret


def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2


for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    used.add(x)
    used.add(y)
    rootX = root(x)
    rootY = root(y)
    if z % 2 == 0:
        unite(x, y)

cnt = 0
uf = {root(n) for n in used}

ans = (len(uf) + 1) // 2 + (N - len(used))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(100000)

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

# Union Find
# N = 100
PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2

used = set()

for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    unite(x, y)

cnt = 0
for i,p in enumerate(PARENT):
    if root(p) == i:
        cnt += 1
print(cnt)

Buggy python submission (verdict: Runtime Error):
N, M = [int(x) for x in input().split()]

# Union Find
# N = 100
PARENT = list(range(N))

used = set()


def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret


def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2


L = []
for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1

    used.add(x)
    used.add(y)
    rootX = root(x)
    rootY = root(y)

    if z % 2 == 0:
        unite(x, y)

cnt = 0
uf = [root(n) for n in PARENT]

ansset = set(uf) - (set(range(N)) - used)

ans = (len(ansset) + 1) // 2 + (N - len(used))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(100000)

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

# Union Find
# N = 100
PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2

used = set()

for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    unite(x, y)

cnt = 0
for i,p in enumerate(PARENT):
    if root(p) == i:
        cnt += 1
print(cnt)
Buggy python submission (verdict: Runtime Error):
A = [int(input())  for _  in range(5)]
k = int(input())

if A[4] - A[0] <= k
    print("Yay!"  )
else:
    print(":(")
         
         


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

if A[4] - A[0] <= k:
    print("Yay!"  )
else:
    print(":(")
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = [int(x) for x in input().split()]
S = input()

for q in range(Q):
    l, r = [int(x) for x in input().split()]
    str = S[l - 1: r]
    # print(str)
    print(str.count('AC'))


Fixed submission:
N, Q = [int(x) for x in input().split()]
S = input()

t = [0] * N
a = [0] * N

for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        t[i] = 1

a[0] = 0
for i in range(N - 1):
    a[i + 1] = a[i] + t[i]

for q in range(Q):
    l, r = [int(x) for x in input().split()]
    print(a[r - 1] - a[l - 1])
Buggy python submission (verdict: Time Limit Exceeded):
A, B = [int(x) for x in input().split()]

ans = B
for i in range(A,B):
    ans = ans ^ i

print(ans)



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

ans = A

for i in range(A + 1, 4 * (1 + A // 4)):
    ans = ans ^ i

for i in range(4 * (B // 4), B + 1):
    ans = ans ^ i

print(ans)
Buggy python submission (verdict: Runtime Error):
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

H, W = [int(x) for x in input().split()]
S = []
for _ in range(H):
    S.append(input())

T = [[0] * W for _ in range(H)]

t = 1


def f(h, w):
    cb = cw = 0
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]

    for i in range(4):
        h2 = h + dh[i]
        w2 = w + dw[i]
        if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
            # 未調査 かつ 色違い
            if T[h2][w2] == 0:
                if S[h][w] != S[h2][w2]:
                    T[h2][w2] = 1
                    if S[h2][w2] == "#":
                        cb += 1
                    if S[h2][w2] == ".":
                        cw += 1
                    cb2, cw2 = f(h2, w2)
                    cb += cb2
                    cw += cw2
    return cb, cw


area = []
for h in range(H):
    for w in range(W):
        if S[h][w] == "#" and T[h][w] == 0:
            tmp = f(h, w)
            if tmp[0]*tmp[1] != 0:
                area.append(tmp)

ans = 0
for a in area:
    ans += a[0]*a[1]

print(ans)



Fixed submission:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

import sys

# input = sys.stdin.readline
sys.setrecursionlimit(400*400*10)
MOD = 10 ** 9 + 7

H, W = [int(x) for x in input().split()]
S = []
for _ in range(H):
    S.append(input())

T = [[0] * W for _ in range(H)]

t = 1


def f(h, w):
    cb = cw = 0
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]

    for i in range(4):
        h2 = h + dh[i]
        w2 = w + dw[i]
        if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
            # 未調査 かつ 色違い
            if T[h2][w2] == 0:
                if S[h][w] != S[h2][w2]:
                    T[h2][w2] = 1
                    if S[h2][w2] == "#":
                        cb += 1
                    if S[h2][w2] == ".":
                        cw += 1
                    cb2, cw2 = f(h2, w2)
                    cb += cb2
                    cw += cw2
    return cb, cw


area = []
for h in range(H):
    for w in range(W):
        if S[h][w] == "#" and T[h][w] == 0:
            tmp = f(h, w)
            if tmp[0]*tmp[1] != 0:
                area.append(tmp)

ans = 0
for a in area:
    ans += a[0]*a[1]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

dp = [0] * (N + 1)

dp[0] = 0
dp[1] = abs(h[0] - h[1])

for n in range(1, N):
    mi = 999999999999
    for k in range(1, K + 1):
        if n - k >= 0:
            t = dp[n - k] + abs(h[n - k] - h[n])
            mi = min(mi, t)
    dp[n] = mi

print(dp[N - 1])


Fixed submission:
N, K = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

dp = [0] * (N + 1)

dp[0] = 0
dp[1] = abs(h[0] - h[1])

for n in range(1, N):
    mi = 999999999999
    for k in range(1, K + 1):
        if n - k >= 0:
            t = dp[n - k] + abs(h[n - k] - h[n])
            mi = min(mi, t)
    dp[n] = mi

print(dp[N - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(x) for x in input().split()]
w = []
v = []

for _ in range(N):
    a, b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)

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

for i in range(1, N + 1):
    for j in range(W + 1):
        a = dp[i - 1][j]
        b = (dp[i - 1][j - w[i - 1]] + v[i - 1]) if j - w[i - 1] >= 0 else 0
        dp[i][j] = max(a, b)

print(dp[N][W])


Fixed submission:
N, W = [int(x) for x in input().split()]
w = []
v = []

for _ in range(N):
    a, b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)

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

for i in range(1, N + 1):
    for j in range(W + 1):
        a = dp[i - 1][j]
        b = (dp[i - 1][j - w[i - 1]] + v[i - 1]) if j - w[i - 1] >= 0 else 0
        dp[i][j] = max(a, b)

print(dp[N][W])