l=[]

n,W=input().split()

n=int(n)

W=int(W)

for i in range(n):

	item=list(map(int,input().split()))

	l.append([item[1],item[0]])



dp=[[False for j in range(W+1)] for i in range(n+1)]



def solve(i,w):

	if dp[i][w]==False:

		if i==n:

			res=(0)

		elif w-l[i][0]<0:

			res=(solve(i+1,w))

		else:

			a=solve(i+1,w)

			b=l[i][1]+solve(i+1,w-l[i][0])

			if b>a:

				res=(b)

			else:

				res=(a)

		dp[i][w]=res

		return(res)

	else:

		return(dp[i][w])



print((solve(0,W)))
value=[0]

weight=[0]

n,W=input().split()

n=int(n)

W=int(W)

for i in range(n):

	item=list(map(int,input().split()))

	value.append(item[0])

	weight.append(item[1])



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

for i in range(n+1):

	for j in range(W+1):

		if i==0:

			res=0

		elif j-weight[i]<0:

			res=dp[i-1][j]

		else:

			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])

		dp[i][j]=res

print((dp[n][W]))
l = []
n, W = input().split()
n = int(n)
W = int(W)
for i in range(n):
    item = list(map(int, input().split()))
    l.append([item[1], item[0]])
dp = [[False for j in range(W + 1)] for i in range(n + 1)]


def solve(i, w):
    if dp[i][w] == False:
        if i == n:
            res = 0
        elif w - l[i][0] < 0:
            res = solve(i + 1, w)
        else:
            a = solve(i + 1, w)
            b = l[i][1] + solve(i + 1, w - l[i][0])
            if b > a:
                res = b
            else:
                res = a
        dp[i][w] = res
        return res
    else:
        return dp[i][w]


print((solve(0, W)))

value = [0]
weight = [0]
n, W = input().split()
n = int(n)
W = int(W)
for i in range(n):
    item = list(map(int, input().split()))
    value.append(item[0])
    weight.append(item[1])
dp = [[0 for j in range(W + 1)] for i in range(n + 1)]
for i in range(n + 1):
    for j in range(W + 1):
        if i == 0:
            res = 0
        elif j - weight[i] < 0:
            res = dp[i - 1][j]
        else:
            res = max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j])
        dp[i][j] = res
print((dp[n][W]))

-l = [] +value = [0] +weight = [0] -    l.append([item[1], item[0]]) -dp = [[False for j in range(W + 1)] for i in range(n + 1)] - - -def solve(i, w): -    if dp[i][w] == False: -        if i == n: +    value.append(item[0]) +    weight.append(item[1]) +dp = [[0 for j in range(W + 1)] for i in range(n + 1)] +for i in range(n + 1): +    for j in range(W + 1): +        if i == 0: -        elif w - l[i][0] < 0: -            res = solve(i + 1, w) +        elif j - weight[i] < 0: +            res = dp[i - 1][j] -            a = solve(i + 1, w) -            b = l[i][1] + solve(i + 1, w - l[i][0]) -            if b > a: -                res = b -            else: -                res = a -        dp[i][w] = res -        return res -    else: -        return dp[i][w] - - -print((solve(0, W))) +            res = max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]) +        dp[i][j] = res +print((dp[n][W]))