import sys

input = sys.stdin.readline



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

dp = [0] * (W + 1)



for _ in range(N):

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

    for i in range(W, w - 1, -1):

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



print((dp[W]))
def main():

    import sys

    input = sys.stdin.readline



    import numpy as np



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

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



    for _ in range(N):

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

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

        

        # for i in range(W, w - 1, -1):

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



    print((dp[W]))



if __name__ == '__main__':

    main()
import sys

input = sys.stdin.readline
N, W = list(map(int, input().split()))
dp = [0] * (W + 1)
for _ in range(N):
    w, v = list(map(int, input().split()))
    for i in range(W, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)
print((dp[W]))

def main():
    import sys

    input = sys.stdin.readline
    import numpy as np

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


if __name__ == "__main__":
    main()

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