Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02995 (python)

Fixed submission:
import sys
import fractions
def input(): return sys.stdin.readline().rstrip()

def main():
    a, b, c, d = map(int, input().split())
    cd_gcd = c * d // fractions.gcd(c, d)
    cnt = lambda n: n - n // c - n // d + n // cd_gcd
    print(cnt(b) - cnt(a-1))

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
import math
import fractions
def input(): return sys.stdin.readline().rstrip()

def main():
    a, b, c, d = map(int, input().split())
    def count_ab(n):
        return math.floor(b / n) - math.ceil(a / n) + 1
    c_cnt = count_ab(c)
    d_cnt = count_ab(d)
    cd_cnt = count_ab(c * d // fractions.gcd(c, d))

    print(b - a - c_c - d_c + cd_c + 1)

if __name__ == '__main__':
    main()
Problem p03044 (python)

Fixed submission:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())

    graph = defaultdict(lambda : defaultdict(int))
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        graph[u][v] = w
        graph[v][u] = w

    depth = [-1] * (N)
    depth[0] = 0
    def dfs(x):
        for i, g in graph[x].items():
            if depth[i] > -1:
                continue
            depth[i] = depth[x] + g
            dfs(i)
    dfs(0)
    print("\n".join(['1' if d % 2 == 0 else '0' for d in depth]))

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    UVW = [tuple(map(int, input().split())) for _ in range(N - 1)]

    ans = ['0'] * N
    fixed = set()
    for u, v, w in UVW:
        if w % 2 == 1:
            if u in fixed:
                ans[v] = '1'
            else:
                ans[u] = '1'
            fixed.add(u)
            fixed.add(v)
    print("\n".join(ans))

if __name__ == '__main__':
    main()
Problem p03078 (python)

Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split())) for _ in range(3)]

    AB = [a + b for a in A for b in B]
    AB = sorted(AB, reverse=True)[:K]

    ABC = [ab + c for ab in AB for c in C]
    ABC = sorted(ABC, reverse=True)[:K]
    for i in ABC:
        print(i)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split())) for _ in range(3)]

    AB = [0] * (X*Y)
    for i, a in enumerate(A):
        for j, b in enumerate(B):
            AB[i * Y + j] = a + b
    
    ans = [0] * (X*Y*Z)
    for i, ab in enumerate(AB):
        for j, c in enumerate(C):
            ans[i * Z + j] = ab + c
    ans = sorted(ans, reverse=True)[:K]
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()
Problem p03282 (python)

Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    K = int(input())
    if len(S) > K and S[K-1] == '1':
        print('1')
        exit()
    for i in list(S):
        if i != '1':
            print(i)
            exit()
    print('1')

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    K = int(input())
    if S[K-1] == '1':
        print('1')
    for i in list(S):
        if i != '1':
            print(i)
            exit()
    print('1')

if __name__ == '__main__':
    main()
Problem p02630 (python)

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

N = int(input())
A = list(map(int, input().split()))
cnt = defaultdict(int)
S = sum(A)
for a in A:
    cnt[a] += 1

Q = int(input())

for _ in range(Q):
    b, c = map(int, input().split())
    num_of_b = cnt[b]
    S += num_of_b * c - num_of_b * b
    cnt[c] += num_of_b
    cnt[b] -= num_of_b

    print(S)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import bisect
import numpy as np
import math
from collections import deque
from collections import defaultdict
from math import gcd

N = int(input())
A = list(map(int, input().split()))
cnt = defaultdict(int)
S = np.sum(A)
for a in A:
    cnt[a] += 1

Q = int(input())

for _ in range(Q):
    b, c = map(int, input().split())
    num_of_b = cnt[b]
    S -= num_of_b * b
    S += num_of_b * c
    cnt[c] += num_of_b

    print(S)
Problem p02947 (python)

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

def get_sum(num):
    return num*(num-1)/2


N = int(input())
S = []
D = defaultdict(int)
ans = 0
for _ in range(N):
    s = str(sorted(input()))
    D[s] += 1

for k, v in D.items():
    ans += get_sum(v)


print(int(ans))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
import sys
input = sys.stdin.readline

def get_sum(num):
    return num*(num-1)/2


N = int(input())
S = []
D = defaultdict(int)
ans = 0
for _ in range(N):
    inp = input()
    inp.sort()
    s = str(inp)
    D[s] += 1

for k, v in D.items():
    ans += get_sum(v)


print(int(ans))
Problem p02983 (python)

Fixed submission:
import sys

input = sys.stdin.readline

L, R = map(int, input().split())

def main():
    if R // 2019 != L // 2019:
        ans = 0
    else:
        # ansLi = L % 2019
        # ansLj = (L+1) % 2019
        # ansL = ansLi * ansLj

        # ansRi = R % 2019
        # ansRj = (R-1) % 2019
        # ansR = ansRi * ansRj
        ansL = L*(L+1) % 2019
        ansR = R*(R-1) % 2019

        ans = min(ansL, ansR)

    return int(ans)

# print(main())

def search_all():
    if R // 2019 != L // 2019:
        return 0
    ans = float("inf")
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(i*j % 2019, ans)
            if ans == 0:
                break
    return ans

print(search_all())

Buggy submission (verdict: Runtime Error):
import sys

input = sys.stdin.readline

L, R = map(int, input().split())

def main():
    LR = list(range(L, R+1))
    N = len(LR)
    if N >= 2019:
        ans = 0
    else:
        ansLi = LR[0] % 2019
        ansLj = LR[1] % 2019
        ansL = ansLi * ansLj

        ansRi = LR[-1] % 2019
        ansRj = LR[-2] % 2019
        ansR = ansRi * ansRj

        ans = min(ansL, ansR)

    return ans

print(main())

Buggy submission (verdict: Runtime Error):
import sys
import bisect

input = sys.stdin.readline

L, R = map(int, input().split())

LR = list(range(L, R+1))
N = len(LR)
index = bisect.bisect_left(LR, 2019)
if index == 0:
    i, j = LR[0], LR[1]
elif index == N:
    i, j = LR[-2], LR[-1]
else:
    i, j = LR[index-1], LR[index]

modi = i % 2019
modj = j % 2019
print(modi * modj)
Problem p02991 (python)

Fixed submission:
# SからTの長さが3の倍数の最短バスを求める
N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)

S, T = map(int, input().split())
S -= 1
T -= 1

from collections import deque

def bfs(start, terminal):
    q = deque([(start, 0)])
    color = [[0]*3 for _ in range(N)]
    d = [[-1]*3 for _ in range(N)]
    d[start][0] = 0
    l = 0
    while len(q) > 0:
        u, l = q.popleft()
        nl = (l + 1) % 3
        for v in G[u]:
            if color[v][nl] == 0:
                q.append((v, nl))
                color[v][nl] = 1
                d[v][nl] = d[u][l] + 1
    
    if d[terminal][0] == -1:
        return -1
    else:
        return d[terminal][0] // 3 

print(bfs(S, T))

Buggy submission (verdict: Runtime Error):

# # import itertools

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

# # def com(n, r):
# #     a = len(list(itertools.combinations(range(n), r)))
# #     return a


from collections import defaultdict

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)

S, T = map(int, input().split())
S -= 1
T -= 1

d = defaultdict(int)
ans = []
def dfs(u, path, num, dis):
    global ans
    path += str(u)
    if len(path) == 4 and d[path] != 0:
        ans.append(10**5)
        return

    if u == T and num % 3 == 0:
        ans.append(int(dis / 3))
        return
    if len(path) == 4:
        d[path] += 1
        path = ""
    for v in G[u]:
        dfs(v, path, num+1, dis+1)

dfs(S, path="", num=0, dis=0)
if len(ans) == 0:
    print(-1)
else:
    a = min(ans)
    if a == 10**5:
        print(-1)
    else:
        print(a)

Buggy submission (verdict: Runtime Error):

# # import itertools

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

# # def com(n, r):
# #     a = len(list(itertools.combinations(range(n), r)))
# #     return a


from collections import defaultdict

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)

S, T = map(int, input().split())
S -= 1
T -= 1

d = defaultdict(int)
ans = 0
def dfs(u, path, num, dis):
    global ans
    path += str(u)
    if d[path] != 0:
        ans = -1
        return

    if u == T and num % 3 == 0:
        ans = int(dis / 3)
        return
    if len(path) == 4:
        d[path] += 1
        path = ""
    for v in G[u]:
        dfs(v, path, num+1, dis+1)

dfs(S, path="", num=0, dis=0)
if ans == 0:
    print(-1)
else:
    print(ans)
Problem p02994 (python)

Fixed submission:
import numpy as np

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

aji = [L + i for i in range(N)]

abs_aji = [abs(a) for a in aji]
index = np.argmin(abs_aji)
aji.pop(index)

print(sum(aji))

Buggy submission (verdict: Runtime Error):
import numpy as np

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

aji = [L + i for i in range(N)]

abs_aji = [abs(a) for a in aji]
index = np.argmin(abs_aji)
aji.pop(index)

print(sum(aji))
Problem p02996 (python)

Fixed submission:
import numpy as np

N = int(input())

A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


def yes_or_no():
    sorted_index = np.argsort(B)
    if A[sorted_index[0]] > B[sorted_index[0]]:
        return 0
    sum_A = [A[sorted_index[0]]]
    for i in range(1, N):
        next_num = sum_A[i-1] + A[sorted_index[i]]
        sum_A.append(next_num)
        if next_num > B[sorted_index[i]]:
            return 0
        
    return 1

if yes_or_no():
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
import numpy as np

N = int(input())

A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


def yes_or_no():
    for c in C:
        if c < 0:
            return 0
    
    sorted_index = np.argsort(B)
    sum_A = [A[sorted_index[0]]]
    for i in range(1, N):
        next_num = sum_A[i-1] + A[sorted_index[i]]
        sum_A.append(next_num)
        if next_num > B[sorted_index[i]]:
            print(sum_A)
            return 0
        
    return 1

if yes_or_no():
    print("Yes")
else:
    print("No")
Problem p03000 (python)

Fixed submission:
N, X = map(int, input().split())
*L, = map(int, input().split())

D = [0]
for i in range(1, N+1):
    D.append(D[i-1] + L[i-1])

num = 0
i = 0
d = D[i]
while d <= X and num < N+1:
    num += 1
    i += 1
    if i != N+1:
        d = D[i]

print(num)

Buggy submission (verdict: Runtime Error):
N, X = map(int, input().split())
*L, = map(int, input().split())

D = [0]
for i in range(1, N+1):
    D.append(D[i-1] + L[i-1])

num = 0
i = 0
d = D[i]
while d <= X and num < N+1:
    num += 1
    i += 1
    d = D[i]

print(num)

Buggy submission (verdict: Runtime Error):
N, X = map(int, input().split())
*L, = map(int, input().split())

D = [0]
for i in range(1, N+1):
    D.append(D[i-1] + L[i-1])

num = 0
i = 0
d = D[i]
while d <= X:
    num += 1
    i += 1
    d = D[i]
print(num)
Problem p03031 (python)

Fixed submission:
import itertools

N, M = map(int, input().split())
S = []
for i in range(M):
    tmp = list(map(int, input().split()))
    S.append([tmp[1:]])
P = list(map(int, input().split()))


origin_list = [0, 1]
all_way = []
for i in itertools.product(origin_list, repeat=N):
    all_way.append(i)

ans = 0
for way in all_way:
    light = 0
    for i, s in enumerate(S):
        small_sum = 0
        for ss in s:
            for sss in ss:
                if way[sss - 1] == 1:
                    small_sum += 1
            if small_sum % 2 == P[i]:
                light += 1
        if light == M:
            ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
import itertools

N, M = map(int, input().split())
S = []
for i in range(M):
    tmp = list(map(int, input().split()))
    S.append([tmp[1:]])
P = list(map(int, input().split()))


origin_list = [0, 1]
all_way = []
for i in itertools.product(origin_list, repeat=N):
    all_way.append(i)

ans = 0
for way in all_way:
    light = 0
    for i, s in enumerate(S):
        small_sum = 0
        for ss in s:
            if way[ss - 1] == 1:
                small_sum += 1
        if small_sum % 2 == P[i]:
            light += 1
    if light == M:
        ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
import itertools

N, M = map(int, input().split())
S = []
for i in range(M):
    tmp = list(map(int, input().split()))
    S.append([tmp[1:]])
P = list(map(int, input().split()))


origin_list = [0, 1]
all_way = []
for i in itertools.product(origin_list, repeat=N):
    all_way.append(i)
print(all_way)

ans = 0
for way in all_way:
    light = 0
    for i, s in enumerate(S):
        small_sum = 0
        for ss in s:
            if way[ss - 1] == 1:
                small_sum += 1
        if small_sum % 2 == P[i]:
            light += 1
    if light == M:
        ans += 1

print(ans)
Problem p03060 (python)

Fixed submission:
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

answer = 0
for i in range(N):
  if V[i] > C[i]:
    answer += V[i] - C[i]

print(int(answer))

Buggy submission (verdict: Runtime Error):
N = int(input())
V = map(int, input().split())
C = map(int, input().split())

answer = 0
for i in range(N):
  if V[i] > C[i]:
    answer += V[i] - C[i]

print(int(answer))
Problem p03061 (python)

Fixed submission:
import fractions

N = int(input())
A = list(map(int, input().split()))

L, R = [0], [0]
for i in range(N):
    L.append(fractions.gcd(L[i], A[i]))
    R.append(fractions.gcd(R[i], A[-i-1]))
L.append(0)
R.append(0)
R = R[::-1]

M = []
for i in range(N):
    M.append(fractions.gcd(L[i], R[i+2]))
print(max(M))

Buggy submission (verdict: Runtime Error):
import functools
import math

N = int(input())
A = list(map(int, input().split()))
answer = 0
for i in range(N):
  tmp = A.copy()
  tmp.pop(i)
  gcd = functools.reduce(math.gcd, tmp)
  
  if answer < gcd:
    answer = gcd

print(int(answer))
Problem p03109 (python)

Fixed submission:
import numpy as np

s = str(input())
y, m, d = s.split("/")

y, m, d = int(y), int(m), int(d)

if y < 2019:
  print("Heisei")
elif y==2019 and m<4:
  print("Heisei")
elif y==2019 and m==4 and d <= 30:
  print("Heisei")
else:
  print("TBD")

Buggy submission (verdict: Runtime Error):
import numpy as np

s = str(input())

y, m, d = s.split("/")

y, m, d = int(y), int(m), int(d)

if y < 2019:
  print("Heisei")
elif y==2019 and m<4:
  print("Heisei")
elif y==2019 and m=4 and d < 30:
  print("Heisei")
else:
  print("TBD")
Problem p03110 (python)

Fixed submission:

N = input()
input = [input() for i in range(int(N))]

temp = []
for s in input:
  v, k = s.split()
  if k == "BTC":
    temp.append(float(v)*380000)
  else:
    temp.append(float(v))

print(sum(temp))

Buggy submission (verdict: Runtime Error):
import numpy as np

N = input()
input = [input() for i in range(N)]

temp = []
for s in input:
  v, k = s.split()
  if k == "BTC":
    temp.append(float(v)*380000)
  else:
    temp.append(float(v))

print(sum(temp))
Problem p03161 (python)

Fixed submission:
import sys
import numpy as np

input = sys.stdin.readline

N, K = map(int, input().split())
*T, = map(int, input().split())

INF = float("inf")  # pythonでの無限大の作り方
DP = [INF for i in range(N)]

def chmin(a, b):
     if a > b:
          return b
     return a

DP[0] = 0
"""
# 2重for文ではTLE
for i in range(1, N):
    for j in range(1, K+1):
        if i-j >= 0:
            DP[i] = chmin(DP[i], DP[i-j] + abs(T[i-j] - T[i]))
"""
"""
# list内包表記でもTLE (2重for文よりはマシ)
for i in range(1, N):
    DP[i] = min([chmin(DP[i], DP[i-j] + abs(T[i-j] - T[i])) for j in range(1, K+1) if i-j >= 0])
"""

DP = np.zeros(N, dtype=int)
T = np.array(T)

for i in range(1, N):
    start = max(0, i-K)
    DP[i] = min(DP[start:i] + np.abs(T[i] - T[start:i]))

print(int(DP[-1]))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
*T, = map(int, input().split())

INF = float("inf")  # pythonでの無限大の作り方
DP = [INF for i in range(N)]

def chmin(a, b):
     if a > b:
          return b
     return a

DP[0] = 0
for i in range(1, N):
    for j in range(1, K+1):
        DP[i+j] = chmin(DP[i+j], DP[i] + abs(T[i+j] - T[i]))

print(int(DP[-1]))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
*T, = map(int, input().split())

INF = float("inf")  # pythonでの無限大の作り方
DP = [INF for i in range(N)]

def chmin(a, b):
     if a > b:
          return b
     return a

DP[0] = 0
for i in range(1, N):
    for j in range(1, K+1):
        if i-j >= 0:
            DP[i+j] = chmin(DP[i+j], DP[i] + abs(T[i+j] - T[i]))

print(int(DP[-1]))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
*T, = map(int, input().split())

INF = float("inf")  # pythonでの無限大の作り方
DP = [INF for i in range(N)]

def chmin(a, b):
     if a > b:
          return b
     return a

DP[0] = 0
for i in range(1, N):
    for j in range(1, K+1):
        DP[i] = chmin(DP[i], DP[i-j] + abs(T[i-j] - T[i]))

print(int(DP[-1]))
Problem p03163 (python)

Fixed submission:
N, W = map(int, input().split())
#i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

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

print(dp[-1][-1])

Buggy submission (verdict: Runtime Error):
# import numpy as np

# N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
# """
# dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
#          = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
# """
# for i in range(1, N+1):
#     wi, vi = map(int, input().split())
#     for k in range(1, i+1):
#         tmp = np.maximum(dp[i-k, :W-wi+1] + vi, dp[i-k, wi:W+1])
#         dp[i, wi:W+1] = np.maximum(dp[i, wi:W+1], tmp)
    

# print(int(dp[-1,-1]))


N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

def maximum(list1, list2):
    ans = []
    for i in range(len(list1)):
        ans.append(max(list1[i], list2[i]))
    return ans

for i in range(1, N+1):
    wi, vi = map(int, input().split())
    for k in range(1, i+1):
        tmp2 = [val + vi for val in dp[i-k][:W-wi+1]]
        tmp = maximum(tmp2, dp[i-k][wi:W+1].copy())
        dp[i][wi:W+1] = maximum(dp[i][wi:W+1], tmp)
    

print(int(dp[-1][-1]))

Buggy submission (verdict: Runtime Error):
import numpy as np

N, W = map(int, input().split())
dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""
for i in range(1, N+1):
    wi, vi = map(int, input().split())
    for k in range(1, i+1):
        tmp = np.maximum(dp[i-k, :W-wi+1] + vi, dp[i-k, wi:W+1])
        dp[i, wi:W+1] = np.maximum(dp[i, wi:W+1], tmp)
    

print(int(dp[-1,-1]))
Problem p03164 (python)

Fixed submission:
#pypy3でAC

import sys
def input():
    return sys.stdin.readline()[:-1]

N, W = map(int, input().split())
w, v = [], []
for i in range(1, N+1):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

V = sum(v)
#i個目までの品物から価値がj以上になるように選んだときの重さの最小値
dp = [[float("inf")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
"""
i番目を選ぶ場合
dp[i][j] = dp[i-1][j-v] + w
i番目を選ばない場合
dp[i][j] = dp[i-1][j]
"""

for i in range(1, N+1):
    for j in range(V+1):
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i-1])
        else:
            dp[i][j] = dp[i-1][j]

# dp[N][j]がW以下であるような最大のjを探す
for j in range(V+1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Buggy submission (verdict: Runtime Error):

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# import numpy as np

# N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
# """
# dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
#          = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
# """
# for i in range(1, N+1):
#     wi, vi = map(int, input().split())
#     for k in range(1, i+1):
#         tmp = np.maximum(dp[i-k, :W-wi+1] + vi, dp[i-k, wi:W+1])
#         dp[i, wi:W+1] = np.maximum(dp[i, wi:W+1], tmp)
    

# print(int(dp[-1,-1]))


N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

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

print(dp[-1][-1])