from collections import defaultdict



def main():

    num, weigh = list(map(int, input().split()))

    dp = [defaultdict(int) for i in range(num + 1)]

    dp[0][0] = 0



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

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

        for pre_value in list(dp[i - 1].keys()):

            dp[i][pre_value] = max(dp[i - 1][pre_value], dp[i][pre_value])

            if pre_value + data[0] <= weigh:

                dp[i][pre_value + data[0]] = max(dp[i - 1][pre_value] + data[1], dp[i][pre_value + data[0]])



    print((max(list(dp[-1].values()))))





if __name__ == '__main__':

    main()

import numpy as np



def main():

    num, weigh = list(map(int, input().split()))

    dp = np.zeros((num + 1, weigh + 1), dtype=int)



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

        now_weigh, now_value = list(map(int, input().split()))

        dp[i, :now_weigh] = dp[i - 1, :now_weigh]

        dp[i, now_weigh:] = np.maximum(dp[i - 1, :weigh - now_weigh + 1] + now_value, dp[i - 1, now_weigh:])



    print((dp[-1][-1]))





if __name__ == '__main__':

    main()



from collections import defaultdict


def main():
    num, weigh = list(map(int, input().split()))
    dp = [defaultdict(int) for i in range(num + 1)]
    dp[0][0] = 0
    for i in range(1, num + 1):
        data = list(map(int, input().split()))
        for pre_value in list(dp[i - 1].keys()):
            dp[i][pre_value] = max(dp[i - 1][pre_value], dp[i][pre_value])
            if pre_value + data[0] <= weigh:
                dp[i][pre_value + data[0]] = max(
                    dp[i - 1][pre_value] + data[1], dp[i][pre_value + data[0]]
                )
    print((max(list(dp[-1].values()))))


if __name__ == "__main__":
    main()

import numpy as np


def main():
    num, weigh = list(map(int, input().split()))
    dp = np.zeros((num + 1, weigh + 1), dtype=int)
    for i in range(1, num + 1):
        now_weigh, now_value = list(map(int, input().split()))
        dp[i, :now_weigh] = dp[i - 1, :now_weigh]
        dp[i, now_weigh:] = np.maximum(
            dp[i - 1, : weigh - now_weigh + 1] + now_value, dp[i - 1, now_weigh:]
        )
    print((dp[-1][-1]))


if __name__ == "__main__":
    main()

-from collections import defaultdict +import numpy as np -    dp = [defaultdict(int) for i in range(num + 1)] -    dp[0][0] = 0 +    dp = np.zeros((num + 1, weigh + 1), dtype=int) -        data = list(map(int, input().split())) -        for pre_value in list(dp[i - 1].keys()): -            dp[i][pre_value] = max(dp[i - 1][pre_value], dp[i][pre_value]) -            if pre_value + data[0] <= weigh: -                dp[i][pre_value + data[0]] = max( -                    dp[i - 1][pre_value] + data[1], dp[i][pre_value + data[0]] -                ) -    print((max(list(dp[-1].values())))) +        now_weigh, now_value = list(map(int, input().split())) +        dp[i, :now_weigh] = dp[i - 1, :now_weigh] +        dp[i, now_weigh:] = np.maximum( +            dp[i - 1, : weigh - now_weigh + 1] + now_value, dp[i - 1, now_weigh:] +        ) +    print((dp[-1][-1]))