def solve_knapsack(s, n, v, w):

	dp = [[0 for x in range(s+1)] for x in range(n+1)]	

	for i in range(n):

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

			if w[i] > j:

				dp[i+1][j] = dp[i][j]

			else:

				dp[i+1][j] = max(dp[i][j], max(dp[i+1][j-w[i]]+v[i], dp[i][j-w[i]]+v[i]))

	return dp[n][s]

	

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

v = [0]*n

w = [0]*n

for i in range(n):

	v[i], w[i] = list(map(int, input().split()))

print((solve_knapsack(s, n, v, w)))





def knapsack(n,W,v,w):

	dp=[[0 for x in range(W+1)] for x in range(n+1)]

	for i in range(n):

		vl = v[i]

		wt = w[i]

		for j in range(W+1):

			if j < w[i]:

				dp[i+1][j]=dp[i][j]

			else:

				dp[i+1][j]=max(dp[i][j],max(dp[i][j-wt]+vl,dp[i+1][j-wt]+vl))

	return dp[n][W]



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

v = [0]*n

w = [0]*n

for i in range(n):

	v[i],w[i] = list(map(int,input().split()))

print((knapsack(n,W,v,w)))



def solve_knapsack(s, n, v, w):
    dp = [[0 for x in range(s + 1)] for x in range(n + 1)]
    for i in range(n):
        for j in range(1, s + 1):
            if w[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(
                    dp[i][j], max(dp[i + 1][j - w[i]] + v[i], dp[i][j - w[i]] + v[i])
                )
    return dp[n][s]


n, s = list(map(int, input().split()))
v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = list(map(int, input().split()))
print((solve_knapsack(s, n, v, w)))

def knapsack(n, W, v, w):
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(n):
        vl = v[i]
        wt = w[i]
        for j in range(W + 1):
            if j < w[i]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(
                    dp[i][j], max(dp[i][j - wt] + vl, dp[i + 1][j - wt] + vl)
                )
    return dp[n][W]


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

-def solve_knapsack(s, n, v, w): -    dp = [[0 for x in range(s + 1)] for x in range(n + 1)] +def knapsack(n, W, v, w): +    dp = [[0 for x in range(W + 1)] for x in range(n + 1)] -        for j in range(1, s + 1): -            if w[i] > j: +        vl = v[i] +        wt = w[i] +        for j in range(W + 1): +            if j < w[i]: -                    dp[i][j], max(dp[i + 1][j - w[i]] + v[i], dp[i][j - w[i]] + v[i]) +                    dp[i][j], max(dp[i][j - wt] + vl, dp[i + 1][j - wt] + vl) -    return dp[n][s] +    return dp[n][W] -n, s = list(map(int, input().split())) +n, W = list(map(int, input().split())) -print((solve_knapsack(s, n, v, w))) +print((knapsack(n, W, v, w)))