N, W = [int(item) for item in input().split()]

item = [[int(item) for item in input().split()] for _ in range(N)]



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



for i in range(N):

    for w in range(W+1):

        if 0 <= w - item[i][0]:

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

        else:

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

print((dp[N][W]))

import sys

input = sys.stdin.readline

import numpy as np



def main():

    N, W = [int(item) for item in input().split()]

    item = np.array([[int(item) for item in input().split()] for _ in range(N)])



    dp = np.zeros((N+1, W+1), dtype='int64')



    for i in range(N):

        dp[i+1] = dp[i]

        w, v = item[i]

        np.maximum(dp[i][:-w] + v, dp[i][w:], out=dp[i+1][w:])

        # print(dp[i+1])

    print((dp[N][W]))



if __name__ == "__main__":

    main()
N, W = [int(item) for item in input().split()]
item = [[int(item) for item in input().split()] for _ in range(N)]
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        if 0 <= w - item[i][0]:
            dp[i + 1][w] = max(dp[i][w], dp[i][w - item[i][0]] + item[i][1])
        else:
            dp[i + 1][w] = dp[i][w]
print((dp[N][W]))

import sys

input = sys.stdin.readline
import numpy as np


def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])
    dp = np.zeros((N + 1, W + 1), dtype="int64")
    for i in range(N):
        dp[i + 1] = dp[i]
        w, v = item[i]
        np.maximum(dp[i][:-w] + v, dp[i][w:], out=dp[i + 1][w:])
        # print(dp[i+1])
    print((dp[N][W]))


if __name__ == "__main__":
    main()

-N, W = [int(item) for item in input().split()] -item = [[int(item) for item in input().split()] for _ in range(N)] -dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] -for i in range(N): -    for w in range(W + 1): -        if 0 <= w - item[i][0]: -            dp[i + 1][w] = max(dp[i][w], dp[i][w - item[i][0]] + item[i][1]) -        else: -            dp[i + 1][w] = dp[i][w] -print((dp[N][W])) +import sys + +input = sys.stdin.readline +import numpy as np + + +def main(): +    N, W = [int(item) for item in input().split()] +    item = np.array([[int(item) for item in input().split()] for _ in range(N)]) +    dp = np.zeros((N + 1, W + 1), dtype="int64") +    for i in range(N): +        dp[i + 1] = dp[i] +        w, v = item[i] +        np.maximum(dp[i][:-w] + v, dp[i][w:], out=dp[i + 1][w:]) +        # print(dp[i+1]) +    print((dp[N][W])) + + +if __name__ == "__main__": +    main()