# -*- coding: utf-8 -*-

"""

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=jp

"""

import sys

input = sys.stdin.readline





def solve_knapsack(weight, items):

    dp = [[0]*(weight+1) for _ in range(len(items))]

    for i, item in enumerate(items[1:]):

        for w in range(1, weight+1):

            if item[1] <= w:

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

            else:

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

    return dp[-1][-1]





def main(args):

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

    items = [[]]

    for _ in range(N):

        items.append([int(x) for x in input().strip().split()])

    result = solve_knapsack(W, items)

    print(result)





if __name__ == '__main__':

    main(sys.argv[1:])
# -*- coding: utf-8 -*-

"""

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=jp

AC

"""

import sys

input = sys.stdin.readline





def solve_knapsack(weight, items):

    dp = [[0]*(weight+1) for _ in range(len(items))]

    for i, item in enumerate(items[1:]):

        for w in range(1, weight+1):

            if item[1] <= w:

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

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

            else:

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

    return dp[-1][-1]





def main(args):

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

    items = [[]]

    for _ in range(N):

        items.append([int(x) for x in input().strip().split()])

    result = solve_knapsack(W, items)

    print(result)





if __name__ == '__main__':

    main(sys.argv[1:])
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=jp
"""
import sys

input = sys.stdin.readline


def solve_knapsack(weight, items):
    dp = [[0] * (weight + 1) for _ in range(len(items))]
    for i, item in enumerate(items[1:]):
        for w in range(1, weight + 1):
            if item[1] <= w:
                dp[i + 1][w] = max(
                    (item[0] + dp[i][w - item[1]]),
                    dp[i][w],
                    (item[0] + dp[i + 1][w - item[1]]),
                )
            else:
                dp[i + 1][w] = dp[i][w]
    return dp[-1][-1]


def main(args):
    N, W = list(map(int, input().split()))
    items = [[]]
    for _ in range(N):
        items.append([int(x) for x in input().strip().split()])
    result = solve_knapsack(W, items)
    print(result)


if __name__ == "__main__":
    main(sys.argv[1:])

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=jp
AC
"""
import sys

input = sys.stdin.readline


def solve_knapsack(weight, items):
    dp = [[0] * (weight + 1) for _ in range(len(items))]
    for i, item in enumerate(items[1:]):
        for w in range(1, weight + 1):
            if item[1] <= w:
                # dp[i+1][w] = max((item[0] + dp[i][w-item[1]]),  dp[i][w], (item[0] + dp[i+1][w-item[1]]))
                dp[i + 1][w] = max(dp[i][w], (item[0] + dp[i + 1][w - item[1]]))
            else:
                dp[i + 1][w] = dp[i][w]
    return dp[-1][-1]


def main(args):
    N, W = list(map(int, input().split()))
    items = [[]]
    for _ in range(N):
        items.append([int(x) for x in input().strip().split()])
    result = solve_knapsack(W, items)
    print(result)


if __name__ == "__main__":
    main(sys.argv[1:])

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