def knapsack(sizes, vals, volume):

    n = len(sizes)



    dp = [[0] * (volume+1) for _ in range(n)] # j is 0...volume



    for i in range(n):

        for j in range(volume+1):

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

            if j - sizes[i] >= 0:

                dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i])

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



    return dp[-1][-1]





if __name__ == "__main__":

    n, volume = [int(x) for x in input().split()]

    sizes, vals = [], []

    for _ in range(n):

        s, v = [int(x) for x in input().split()]

        sizes.append(s)

        vals.append(v)

    print((knapsack(sizes, vals, volume)))

def knapsack(sizes, vals, volume):

    n = len(sizes)



    dp = [[0] * (volume+1) for _ in range(n)] # j is 0...volume



    for i in range(n):

        for j in range(volume+1):

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

            if j - sizes[i] >= 0:

                dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i])

            #dp[i][j] = max(dp[i][j], dp[i-1][j])



    return dp[-1][-1]





if __name__ == "__main__":

    n, volume = [int(x) for x in input().split()]

    sizes, vals = [], []

    for _ in range(n):

        s, v = [int(x) for x in input().split()]

        sizes.append(s)

        vals.append(v)

    print((knapsack(sizes, vals, volume)))

def knapsack(sizes, vals, volume):
    n = len(sizes)
    dp = [[0] * (volume + 1) for _ in range(n)]  # j is 0...volume
    for i in range(n):
        for j in range(volume + 1):
            dp[i][j] = max(dp[i][j], dp[i - 1][j])
            if j - sizes[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - sizes[i]] + vals[i])
            dp[i][j] = max(dp[i][j], dp[i - 1][j])
    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print((knapsack(sizes, vals, volume)))

def knapsack(sizes, vals, volume):
    n = len(sizes)
    dp = [[0] * (volume + 1) for _ in range(n)]  # j is 0...volume
    for i in range(n):
        for j in range(volume + 1):
            dp[i][j] = max(dp[i][j], dp[i - 1][j])
            if j - sizes[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - sizes[i]] + vals[i])
            # dp[i][j] = max(dp[i][j], dp[i-1][j])
    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print((knapsack(sizes, vals, volume)))

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