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

v_lis, w_lis = [], []   # in order, list for values, and for weights



# set data

for _ in range(n):

    v, c = list(map(int, input().split()))

    v_lis.append(v)

    w_lis.append(c)



# ?????´???????????????????????´????????§?¨±????????¨??????

# (Outer is for index of products, inner is maximum allowable amount)

dp = [[0 for _ in range(maxw+1)] for _ in range(n+1)]



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

    for j in range(1, maxw+1):

        if j>=w_lis[i-1]:

            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_lis[i-1]]+v_lis[i-1])

        else:

            dp[i][j] = dp[i-1][j]



print((dp[-1][-1]))
n, maxw = list(map(int, input().split()))



dp = [0 for _ in range(maxw+1)]

for i in range(n):

    v, c = list(map(int, input().split()))

    for j in range(maxw, -1, -1):

        if j>=c:

            dp[j] = max(dp[j], dp[j-c]+v)

        else:

            break

print((dp[-1]))
n, maxw = list(map(int, input().split()))
v_lis, w_lis = [], []  # in order, list for values, and for weights
# set data
for _ in range(n):
    v, c = list(map(int, input().split()))
    v_lis.append(v)
    w_lis.append(c)
# ?????´???????????????????????´????????§?¨±????????¨??????
# (Outer is for index of products, inner is maximum allowable amount)
dp = [[0 for _ in range(maxw + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, maxw + 1):
        if j >= w_lis[i - 1]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w_lis[i - 1]] + v_lis[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]
print((dp[-1][-1]))

n, maxw = list(map(int, input().split()))
dp = [0 for _ in range(maxw + 1)]
for i in range(n):
    v, c = list(map(int, input().split()))
    for j in range(maxw, -1, -1):
        if j >= c:
            dp[j] = max(dp[j], dp[j - c] + v)
        else:
            break
print((dp[-1]))

-v_lis, w_lis = [], []  # in order, list for values, and for weights -# set data -for _ in range(n): +dp = [0 for _ in range(maxw + 1)] +for i in range(n): -    v_lis.append(v) -    w_lis.append(c) -# ?????´???????????????????????´????????§?¨±????????¨?????? -# (Outer is for index of products, inner is maximum allowable amount) -dp = [[0 for _ in range(maxw + 1)] for _ in range(n + 1)] -for i in range(1, n + 1): -    for j in range(1, maxw + 1): -        if j >= w_lis[i - 1]: -            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w_lis[i - 1]] + v_lis[i - 1]) +    for j in range(maxw, -1, -1): +        if j >= c: +            dp[j] = max(dp[j], dp[j - c] + v) -            dp[i][j] = dp[i - 1][j] -print((dp[-1][-1])) +            break +print((dp[-1]))