# -*- coding: utf-8 -*-

"""

Created on Sat Mar 23 21:51:02 2019



@author: Yamazaki Kenichi

"""



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

A = [list(map(int,input().split())) for i in range(N)]



ans = [[-1 for i in range(N+1)]]

ans[0][N] = 0

for i in range(1,W+1):

    tmp = -1

    maxv = ans[-1][N]

#    print('aa',maxv)

    for j in range(N):

#        print(i,j,A[j][0],maxv,ans[i -A[j][0]][j])

#        print(i,j,A[j],i -A[j][0],ans[-1])

        if i-A[j][0] >= 0 and ans[i-A[j][0]][j] == -1 and ans[i-A[j][0]][N] + A[j][1] > maxv:

            maxv = ans[i-A[j][0]][N] + A[j][1]

            tmp = j

#            print('maxv',maxv,'tmp',tmp)

    if tmp != -1:

        ans.append(ans[-A[tmp][0]][:])

        ans[i][tmp] = 1

    else:

        ans.append(ans[-1][:])

    ans[i][N] = maxv

#    print(ans[i][N])

#    print(ans[i])

print((ans[W][N]))


import sys

import numpy as np



sys.setrecursionlimit(10 ** 9)



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

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



wv.sort()



ans = 0

dp = np.zeros(W + 1, dtype=int)



for w, v in wv:

    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])



ans = dp[-1]

print(ans)



# -*- coding: utf-8 -*-
"""
Created on Sat Mar 23 21:51:02 2019
@author: Yamazaki Kenichi
"""
N, W = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
ans = [[-1 for i in range(N + 1)]]
ans[0][N] = 0
for i in range(1, W + 1):
    tmp = -1
    maxv = ans[-1][N]
    #    print('aa',maxv)
    for j in range(N):
        #        print(i,j,A[j][0],maxv,ans[i -A[j][0]][j])
        #        print(i,j,A[j],i -A[j][0],ans[-1])
        if (
            i - A[j][0] >= 0
            and ans[i - A[j][0]][j] == -1
            and ans[i - A[j][0]][N] + A[j][1] > maxv
        ):
            maxv = ans[i - A[j][0]][N] + A[j][1]
            tmp = j
    #            print('maxv',maxv,'tmp',tmp)
    if tmp != -1:
        ans.append(ans[-A[tmp][0]][:])
        ans[i][tmp] = 1
    else:
        ans.append(ans[-1][:])
    ans[i][N] = maxv
#    print(ans[i][N])
#    print(ans[i])
print((ans[W][N]))

import sys
import numpy as np

sys.setrecursionlimit(10**9)
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
wv.sort()
ans = 0
dp = np.zeros(W + 1, dtype=int)
for w, v in wv:
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
ans = dp[-1]
print(ans)

-# -*- coding: utf-8 -*- -""" -Created on Sat Mar 23 21:51:02 2019 -@author: Yamazaki Kenichi -""" +import sys +import numpy as np + +sys.setrecursionlimit(10**9) -A = [list(map(int, input().split())) for i in range(N)] -ans = [[-1 for i in range(N + 1)]] -ans[0][N] = 0 -for i in range(1, W + 1): -    tmp = -1 -    maxv = ans[-1][N] -    #    print('aa',maxv) -    for j in range(N): -        #        print(i,j,A[j][0],maxv,ans[i -A[j][0]][j]) -        #        print(i,j,A[j],i -A[j][0],ans[-1]) -        if ( -            i - A[j][0] >= 0 -            and ans[i - A[j][0]][j] == -1 -            and ans[i - A[j][0]][N] + A[j][1] > maxv -        ): -            maxv = ans[i - A[j][0]][N] + A[j][1] -            tmp = j -    #            print('maxv',maxv,'tmp',tmp) -    if tmp != -1: -        ans.append(ans[-A[tmp][0]][:]) -        ans[i][tmp] = 1 -    else: -        ans.append(ans[-1][:]) -    ans[i][N] = maxv -#    print(ans[i][N]) -#    print(ans[i]) -print((ans[W][N])) +wv = [list(map(int, input().split())) for _ in range(N)] +wv.sort() +ans = 0 +dp = np.zeros(W + 1, dtype=int) +for w, v in wv: +    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:]) +ans = dp[-1] +print(ans)