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

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



def knapsack(n,w,wv):

    inf = float('inf')

    dp = [[-inf for _ in range(w+1)] for _ in range(n+1)]

    for i in range(w+1): dp[0][i] = 0



    for i in range(n):

        for w in range(w+1):

            if wv[i][0]<=w:

                dp[i+1][w] = max(dp[i][w-wv[i][0]]+wv[i][1],dp[i][w])

            else:

                dp[i+1][w] = dp[i][w]

    return dp[n][w]



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

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



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



for i in range(n):

    for j in range(w+1):

        if wv[i][0] <= j:

            dp[i+1][j] = max(dp[i][j-wv[i][0]]+wv[i][1],dp[i][j])

        else:

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



print((max(dp[-1])))
n, w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]


def knapsack(n, w, wv):
    inf = float("inf")
    dp = [[-inf for _ in range(w + 1)] for _ in range(n + 1)]
    for i in range(w + 1):
        dp[0][i] = 0
    for i in range(n):
        for w in range(w + 1):
            if wv[i][0] <= w:
                dp[i + 1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])
            else:
                dp[i + 1][w] = dp[i][w]
    return dp[n][w]


print((knapsack(n, w, wv)))

n, w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if wv[i][0] <= j:
            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print((max(dp[-1])))

- - -def knapsack(n, w, wv): -    inf = float("inf") -    dp = [[-inf for _ in range(w + 1)] for _ in range(n + 1)] -    for i in range(w + 1): -        dp[0][i] = 0 -    for i in range(n): -        for w in range(w + 1): -            if wv[i][0] <= w: -                dp[i + 1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w]) -            else: -                dp[i + 1][w] = dp[i][w] -    return dp[n][w] - - -print((knapsack(n, w, wv))) +dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)] +for i in range(n): +    for j in range(w + 1): +        if wv[i][0] <= j: +            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i][j]) +        else: +            dp[i + 1][j] = dp[i][j] +print((max(dp[-1])))