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

Fixed submission:
n = int(input())
def dfs(s):
    if int(s)>n:
        return 0
    res = 1 if all(s.count(c) > 0 for c in '753') else 0
    for i in '753':
        res += dfs(s+i)
    return res
print(dfs('0'))

Buggy submission (verdict: Runtime Error):
n = int(input())
def dfs(s):
    if int(s)>n:
        return 0
    res = 1 if all(s.count(c) > 0 for c in '753') else 0
    for i in '753':
        res += dfs(s+i)
dfs('0')

Buggy submission (verdict: Runtime Error):
n = int(input())
def dfs(s):
    if int(s)>n:
        return 0
    res = 1 if all(s.count(c) > 0 for c in '753') else 0
    for i in '753':
        res += dfs(s+i)
dfs(0)
Problem p03436 (python)

Fixed submission:
from collections import deque
h,w = map(int, input().split())
G = [['#']*(w+2)]
white = 0
for i in range(h):
    G.append(['#']+list(input()) + ['#'])
    white += G[i+1].count('.')
G.append(['#']*(w+2))

G[1][1] = 1
que = deque([[1,1]])
while que:
    y,x = que.popleft()
    d = G[y][x]
    for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        ny = y+dy
        nx = x+dx
        if G[ny][nx] == '.':
            G[ny][nx] = d+1
            que.append((ny,nx))
if G[h][w] == '.':
    print('-1')
else:
    ans = white - G[h][w]
    print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
h,w = map(int, input().split())
G = [['#']*(w+2)]
white = 0
for i in range(h):
    G.append(['#']+list(input()) + ['#'])
    white += G[i+1].count('.')
G.append(['#']*(w+2))

G[1][1] = 1
que = deque([[1,1]])
while que:
    y,x = que.popleft()
    d = G[y][x]
    for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        ny = y+dy
        nx = x+dx
        if G[ny][nx] == '.':
            G[ny][nx] = d+1
            que.append((ny,nx))
ans = white-G[h][w]
print(ans)
Problem p03167 (python)

Fixed submission:
H, W = map(int, input().split())
M = [input() for i in range(H)]
dp = [[0 for i in range(W+1)] for j in range(H+1)]
dp[1][1] = 1

for i in range(1, H+1):
  for j in range(1, W+1):
    if i == 1 and j == 1:
      continue
    if M[i-1][j-1] == "#":
      continue
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[H][W] % (10**9+7))

Buggy submission (verdict: Runtime Error):
H, W = map(int, input().split())
M = [input() for i in range(H)]
dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1

for i in range(H):
  for j in range(W):
    if i+1 < H and M[i+1][j] == ".":
      dp[i+1][j] = dp[i][j]
    if j+1 < W and M[i][j+1] == ".":
      dp[i][j+1] += dp[i][j]

print(dp[H][W] % (10**9+7))
Problem p03434 (python)

Fixed submission:
N = int(input())
cards = sorted(list(map(int, input().split())), reverse=True)

alice = 0
bob = 0
for i in range(N):
  if i % 2 == 0:
    alice += cards[i]
  else:
    bob += cards[i]

print(alice-bob)

Buggy submission (verdict: Runtime Error):
N = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
print(sum(a[::2]-sum(a[1::2])))

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

alice = 0
bob = 0
for i in range(N+1):
  if i % 2 == 0:
    alice += cards[i]
  else:
    bob += cards[i]

print(alice-bob)
Problem p03675 (python)

Fixed submission:
from collections import deque

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

q = deque()
for i in range(N):
  a = A[i]
  if i > 1 and i % 2 == 0:
    q.appendleft(a)
  else:
    q.append(a)

if N % 2 == 0:
  q.reverse()
print(" ".join(map(str, q)))

Buggy submission (verdict: Runtime Error):
from collections import deque

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

q = deque()
q.append(A[0])
q.append(A[1])
for i in range(2, N):
  a = A[i]
  if i % 2 == 1:
    q.appendleft(a)
  else:
    q.append(a)

print(" ".join(map(str, q)))
Problem p02727 (python)

Fixed submission:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    X,Y,a,b,c = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    i,j,k = 0,0,0
    p.sort(reverse=1)
    q.sort(reverse=1)
    r.sort(reverse=1)
    res = 0
    #[値, 種類, インデックス]
    hq = [[-p[0], 0, 0], [-q[0], 1, 0], [-r[0], 2, 0]]
    heapify(hq)
    n = 0
    while X+Y>n:
        x,y,z = heappop(hq)
        res += -x
        n += 1
        if y==0 and z+1<X:
            heappush(hq, [-p[z+1], 0, z+1])
        if y==1 and z+1<Y:
            heappush(hq, [-q[z+1], 1, z+1])
        if y==2 and z+1<c:
            heappush(hq, [-r[z+1], 2, z+1])
    print(res)
        
if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    X,Y,a,b,c = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    i,j,k = 0,0,0
    p.sort(reverse=1)
    q.sort(reverse=1)
    r.sort(reverse=1)
    res = 0
    while k<c and i<X and j<Y:
        s = p[i]
        t = q[j]
        u = r[k]
        if s<t and s<u:
            res += t+u
            j += 1
            k += 1
        elif t<s and t<u:
            res += s+u
            i += 1
            k += 1
        else:
            res += s+t
            i += 1
            j += 1
    if i==X:
        l = q[j:] + r[k:]
        l.sort(reverse=1)
        res += sum(l[:X+Y-i-j-k])
    elif j==Y:
        l = p[i:] + r[k:]
        l.sort(reverse=1)
        res += sum(l[:X+Y-i-j-k])
    else:
        res = 0
        for i in range(X+Y-c):
            if i < X and X+Y-c-i<Y:
                res = max(res, p[:i]+q[:X+Y-c-i])
            else:
                continue
        res += sum(r)
    print(res)


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

Fixed submission:

a,b,c = map(int, input().split())
if c-a-b<0:
    print('No')
else:
    if 4*a*b<(c-a-b)**2:
        print('Yes')
    else:
        print('No')

Buggy submission (verdict: Runtime Error):
a,b,c = map(int, input().split())
if c-a-b<0:
    print('No')
else:
    4*a*b<(c-a-b)**2:
    print('Yes')
Problem p02756 (python)

Fixed submission:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    S = input()
    Q = int(input())
    mae = ''
    usiro = ''
    s = True
    for _ in range(Q):
        q = list(input().split())
        if q[0]=='1':
            s = not s
        else:
            if q[1]=='1' and s:
                mae = q[2] + mae
            elif q[1]=='2' and s:
                usiro = usiro + q[2] 
            elif q[1]=='2' and not s:
                mae = q[2] + mae
            else:
                usiro = usiro + q[2]
    if s:
        print(mae+S+usiro)
    else:
        print(usiro[::-1]+S[::-1]+mae[::-1])




if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from sys import stdin
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    S = input()
    Q = int(input())
    mae = ''
    usiro = ''
    s = True
    for _ in range(Q):
        q = stdin.readline()
        if q[0]=='1':
            s = not s
        else:
            if q[2]=='1' and s:
                mae = q[4] + mae
            elif q[2]=='2' and s:
                usiro = usiro + q[4] 
            elif q[2]=='2' and not s:
                mae = q[4] + mae
            else:
                usiro = usiro + q[4]
    if s:
        print(mae+S+usiro)
    else:
        print(usiro[::-1]+S[::-1]+mae[::-1])




if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from sys import stdin
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    S = input()
    Q = int(input())
    mae = ''
    usiro = ''
    s = True
    for _ in range(Q):
        q = stdin.readline()
        if q[0]=='1':
            s = not s
        else:
            if q[1]=='1' and s:
                mae = q[2] + mae
            elif q[1]=='2' and s:
                usiro = usiro + q[2] 
            elif q[1]=='2' and not s:
                mae = q[2] + mae
            else:
                usiro = usiro + q[2]
    if s:
        print(mae+S+usiro)
    else:
        print(usiro[::-1]+S[::-1]+mae[::-1])




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

Fixed submission:
n,m = map(int, input().split())
if n == m:
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
n,m = int(input())
if n == m:
    print('Yes')
else:
    print('No')
Problem p02861 (python)

Fixed submission:
'''
https://atcoder.jp/contests/abc145/tasks/abc145_c
'''
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N = int(input())
    grid = [list(map(int, input().split())) for _ in range(N)]
    res = 0
    for path in permutations(grid, N):
        for i in range(N-1):
            res += ((path[i][0]-path[i+1][0])**2 + (path[i][1]-path[i+1][1])**2)**0.5
    a = 1
    for i in range(2, N+1):
        a *= i
    print(res/a)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
N=int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
res=0
for i in range(N):
  for j in range(N):
    ans+=((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5
    print(res/N)
Problem p02972 (python)

Fixed submission:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    res = []
    #dp[i]:i番目の箱に入ってるかどうか
    dp = [0]*n

    #iの倍数の箱を調べる
    for i in range(n, 0, -1):
        #調べる箱列挙
        t = 0
        for j in range(i, n+1, i):
            t += dp[j-1]
        if t%2 != a[i-1]:
            res.append(i)
            dp[i-1] = 1

    if not 1 in a:
        print(0)
    else:
        if len(res)>0:
            print(len(res))
            print(*res)
        else:
            print(-1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    res = []
    dp = [0]*n

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2

    for i in range(n-1, -1, -1):
        if (a[i]==1 and dp[i]==0) or (a[i]==0 and dp[i]==1):
            l = yakusuu(a[i])
            res.append(i+1)
            for j in l:
                dp[j] = (dp[j] + 1) % 2
        else:
            continue
    print(len(res))
    if len(res)>0:
        print(' '.join(map(str, res)))

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

Fixed submission:
n = int(input())

d = [input().split() + [i+1] for i in range(n)]
d = sorted(d, key=lambda x:int(x[1]), reverse=True)
d = sorted(d, key=lambda x:x[0], reverse=False)
for s in d:
    print(s[-1])

Buggy submission (verdict: Runtime Error):
n = int(input())

d = [input().split() + [i+1] for i in range(N)]
d = sorted(d, key=lambda x:x[1], reverse=True)
d = sorted(d, key=lambda x:x[0], reverse=False)
for s in d:
    print(s[-1])
Problem p03031 (python)

Fixed submission:
'''
https://atcoder.jp/contests/abc128/tasks/abc128_c
'''
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque

    #mod = 1000000007

    n, m = map(int, input().split())
    switch_list = [list(map(int, input().split())) for _ in range(m)]
    p = list(map(int, input().split()))
    ret = 0
    for j in range(2**n):
        cnt = 0
        for i in range(m):
            total = 0
            for k in switch_list[i][1:]:
                if j & 2**(k-1):
                    total += 1
            if total%2 == p[i]:
                cnt += 1
            else:
                break
        if cnt == m:
            ret += 1
    print(ret)
if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    n, m = map(int, input().split())
    switch_list = [list(map(int, input().split())) for _ in range(m)]
    p = list(map(int, input().split()))
    ret = 0
    for j in range(2**n):
        cnt = 0
        for i in range(m):
            flag = 1
            for k in switch_list[i][1:]:
                if j & 2**(k-1):
                    total += 1
            if not total%2 == p[i]:
                flag = 0
                break
        if flag:
            ret += 1
    print(ret)

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

Fixed submission:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    a,b = map(int, input().split())
    if a >=13:
        print(b)
    elif a<=5:
        print(0)
    else:
        print(b//2)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    mod = 10**9 + 7

    # max_nCrまで調べられる
    max_n = 4*10**5
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod
    
    # nCrを求める
    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

    n,m,k = map(int, input().split())

    base = ncr(n*m-2, k-2)

    res = 0
    # x方向
    for i in range(1, m):
        res += n**2 * i * (m-i)
        res %= mod

    for i in range(1, n):
        res += m**2 * i * (n-i)
        res %= mod

    print(res*base%mod)

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

Fixed submission:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    n,q = map(int, input().split())
    s = input()
    l = [0]*(n+1)
    for i in range(n):
        if s[i:i+2]=='AC':
            l[i+1]=l[i] + 1
        else:
            l[i+1]=l[i]

    for _ in range(q):
        a, b = map(int, input().split())
        print(l[b-1]-l[a-1])


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
N, Q = map(int, input().split())
S = input()
t = [0] * N
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])

Buggy submission (verdict: Runtime Error):
N, Q = map(int, input().split())
S = input()
t = [0] * N
for i in range(N):
 	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
Problem p03128 (python)

Fixed submission:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    #使う本数の種類
    b = set()
    matti = [2,5,5,4,5,6,3,7,6]
    for i in a:
        b.add(matti[i-1])

    dp = [-1]*(n+1)
    dp[0] = 0
    for i in range(n+1):
        for j in b:
            if i >= j:
                dp[i] = max(dp[i-j]+1, dp[i])

    keta = dp[-1]
    res = []
    a.sort(reverse=True)
    cnt = n
    while cnt>0:
        for i in a:
            if cnt >= matti[i-1]:
                if dp[cnt]-dp[cnt-matti[i-1]]==1:
                    res.append(str(i))
                    cnt -= matti[i-1]
                    break
    print(''.join(res))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    #使う本数の種類
    b = set()
    matti = [2,5,5,4,5,6,3,7,6]
    for i in a:
        b.add(matti[i-1])

    dp = [-1]*(n+1)
    dp[0] = 0
    for i in range(n+1):
        for j in b:
            if i >= j:
                dp[i] = max(dp[i-j]+1, dp[i])

    keta = dp[-1]
    res = []
    a.sort(reverse=True)
    cnt = n
    while cnt>0:
        for i in a:
            if dp[cnt]-dp[cnt-matti[i-1]]==1:
                res.append(str(i))
                cnt -= matti[i-1]
                break
    print(''.join(res))

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

Fixed submission:
#カエル
#各足場の1つ前と2つ前を考える

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = float('inf')
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(1, N):
        for j in range(1,K+1):
            if i>=j:
                dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
            else:
                continue
    print(dp[N-1])

if __name__ == '__main__':
    main()

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

    N, K = map(int, input().split())
    H = np.array(list(map(int, input().split())) + [0] * (K + 2), dtype = np.int32) 

    INF = 10 ** 9
    cost = np.array([INF] * (N + K + 2), dtype = np.int32)
    cost[0] = 0

    n_minimum = np.minimum
    n_abs = np.abs

    for i in range(N):
        cost[i + 1: i + K + 1] = n_minimum(cost[i + 1: i + K + 1], cost[i] + n_abs(H[i + 1: i + K + 1] - H[i]))


    # print (cost)
    print (cost[N - 1])
    return

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

Fixed submission:


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N, W = map(int, input().split())
    w = [0]*N
    v = [0]*N
    for i in range(N):
        w[i], v[i] = map(int, input().split())
    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if w[i]<=j:
                dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
            else:
                dp[i+1][j] = dp[i][j]
    print(dp[N][W])
    

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007
    
    N, W = map(int,input().split())
    wv = [tuple(map(int,input().split())) for i in range(n)]
    dp = [0]*(W+1)
    for i in range(N):
        for j in range(W, wv[i][0]-1, -1):
            dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])
    print(max(dp))

if __name__ == '__main__':
    main()