import sys



input = sys.stdin.readline

sys.setrecursionlimit(10 ** 7)





def main():

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

    w = [0]

    v = [0]

    for i in range(N):

        weight, value = list(map(int, input().split()))

        w.append(weight)

        v.append(value)



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





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

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

            if j - w[i] < 0:

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

            else:

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

    # print(w, v, dp)

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





if __name__ == "__main__":

    main()

import sys

import numpy as np



input = sys.stdin.readline

sys.setrecursionlimit(10 ** 7)





def main():

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

    w = [0]

    v = [0]

    for i in range(N):

        weight, value = list(map(int, input().split()))

        w.append(weight)

        v.append(value)



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

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





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

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



    # print(w, v, dp)

    print((dp.max()))





if __name__ == "__main__":

    main()

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**7)


def main():
    N, W = list(map(int, input().split()))
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = list(map(int, input().split()))
        w.append(weight)
        v.append(value)
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, W + 1):
            if j - w[i] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
    # print(w, v, dp)
    print((dp[N][W]))


if __name__ == "__main__":
    main()

import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10**7)


def main():
    N, W = list(map(int, input().split()))
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = list(map(int, input().split()))
        w.append(weight)
        v.append(value)
    # dp = [[0] * (W + 1) for _ in range(N + 1)]
    dp = np.zeros(W + 1, dtype=np.int64)
    for i in range(1, N + 1):
        dp[w[i] :] = np.maximum(dp[w[i] :], dp[: -w[i]] + v[i])
    # print(w, v, dp)
    print((dp.max()))


if __name__ == "__main__":
    main()

+import numpy as np -    dp = [[0] * (W + 1) for _ in range(N + 1)] +    # dp = [[0] * (W + 1) for _ in range(N + 1)] +    dp = np.zeros(W + 1, dtype=np.int64) -        for j in range(1, W + 1): -            if j - w[i] < 0: -                dp[i][j] = dp[i - 1][j] -            else: -                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) +        dp[w[i] :] = np.maximum(dp[w[i] :], dp[: -w[i]] + v[i]) -    print((dp[N][W])) +    print((dp.max()))