from pprint import pprint



n,w = list(map(int,input().split()))



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





dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]



dp_table[0] = [0]*(w+1)



#sum_w以下の重さの時のvalueの合計の最大を求めていく。



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

    for sum_w in range(w+1):

        #i番目の品物を選ばない場合

        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w])

        #i番目の品物を選ぶ場合

        if sum_w >= wv[i-1][0]:

            dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])

        else:

            continue





result = dp_table[n][w]

print(result)

from pprint import pprint



n,w = list(map(int,input().split()))



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





dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]



dp_table[0] = [0]*(w+1)



#sum_w以下の重さの時のvalueの合計の最大を求めていく。



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

    for sum_w in range(w+1):

        #i番目の品物を選ぶ場合

        if sum_w >= wv[i-1][0]:

            dp_table[i][sum_w] = max(dp_table[i-1][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])

        else:

            #i番目の品物を選ばない場合

            dp_table[i][sum_w] = dp_table[i-1][sum_w]





result = dp_table[n][w]

print(result)

from pprint import pprint

n, w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]
dp_table = [[-float("inf")] * (w + 1) for _ in range(n + 1)]
dp_table[0] = [0] * (w + 1)
# sum_w以下の重さの時のvalueの合計の最大を求めていく。
for i in range(1, n + 1):
    for sum_w in range(w + 1):
        # i番目の品物を選ばない場合
        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i - 1][sum_w])
        # i番目の品物を選ぶ場合
        if sum_w >= wv[i - 1][0]:
            dp_table[i][sum_w] = max(
                dp_table[i][sum_w], dp_table[i - 1][sum_w - wv[i - 1][0]] + wv[i - 1][1]
            )
        else:
            continue
result = dp_table[n][w]
print(result)

from pprint import pprint

n, w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]
dp_table = [[-float("inf")] * (w + 1) for _ in range(n + 1)]
dp_table[0] = [0] * (w + 1)
# sum_w以下の重さの時のvalueの合計の最大を求めていく。
for i in range(1, n + 1):
    for sum_w in range(w + 1):
        # i番目の品物を選ぶ場合
        if sum_w >= wv[i - 1][0]:
            dp_table[i][sum_w] = max(
                dp_table[i - 1][sum_w],
                dp_table[i - 1][sum_w - wv[i - 1][0]] + wv[i - 1][1],
            )
        else:
            # i番目の品物を選ばない場合
            dp_table[i][sum_w] = dp_table[i - 1][sum_w]
result = dp_table[n][w]
print(result)

-        # i番目の品物を選ばない場合 -        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i - 1][sum_w]) -                dp_table[i][sum_w], dp_table[i - 1][sum_w - wv[i - 1][0]] + wv[i - 1][1] +                dp_table[i - 1][sum_w], +                dp_table[i - 1][sum_w - wv[i - 1][0]] + wv[i - 1][1], -            continue +            # i番目の品物を選ばない場合 +            dp_table[i][sum_w] = dp_table[i - 1][sum_w]