#!/usr/bin/env python

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



"""

input:

4 5

4 2

5 2

2 1

8 3



output:

13

"""



import sys

from collections import namedtuple





# def solve():

#     for i, item in enumerate(item_list, 1):

#         for cp in range(1, real_cp + 1):

#             # capacity allows putting in, calculate value

#             if item.w <= cp:

#                 values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)

#             # can't put in, skip current item

#             else:

#                 values[i][cp] = values[i - 1][cp]

#

#     return values[c_items][real_cp]





def solve_2():

    dp = [0] * (real_cp + 1)

    for item in item_list:

        v, w = item.v, item.w

        for cp in range(real_cp - w, -1, -1):

            dp[cp + w] = max(dp[cp + w], dp[cp] + v)



    return dp[-1]





if __name__ == '__main__':

    _input = sys.stdin.readlines()

    c_items, real_cp = list(map(int, _input[0].split()))

    items = [x.split() for x in _input[1:]]



    Item = namedtuple('Item', ('v', 'w'))

    item_list = [Item(int(v), int(w)) for v, w in items]



    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]

    print((solve_2()))
#!/usr/bin/env python

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



"""

input:

4 5

4 2

5 2

2 1

8 3



output:

13

"""



import sys

from collections import namedtuple





def solve():

    dp = [0] * (real_cp + 1)

    for item in item_list:

        v, w = item.v, item.w

        # for cp in range(real_cp - w, -1, -1):

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

        for cp in range(real_cp, w - 1, -1):

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



    return dp[-1]





if __name__ == '__main__':

    _input = sys.stdin.readlines()

    c_items, real_cp = list(map(int, _input[0].split()))

    items = [x.split() for x in _input[1:]]



    Item = namedtuple('Item', ('v', 'w'))

    item_list = [Item(int(v), int(w)) for v, w in items]



    print((solve()))
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
4 5
4 2
5 2
2 1
8 3
output:
13
"""
import sys
from collections import namedtuple

# def solve():
#     for i, item in enumerate(item_list, 1):
#         for cp in range(1, real_cp + 1):
#             # capacity allows putting in, calculate value
#             if item.w <= cp:
#                 values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
#             # can't put in, skip current item
#             else:
#                 values[i][cp] = values[i - 1][cp]
#
#     return values[c_items][real_cp]
def solve_2():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        for cp in range(real_cp - w, -1, -1):
            dp[cp + w] = max(dp[cp + w], dp[cp] + v)
    return dp[-1]


if __name__ == "__main__":
    _input = sys.stdin.readlines()
    c_items, real_cp = list(map(int, _input[0].split()))
    items = [x.split() for x in _input[1:]]
    Item = namedtuple("Item", ("v", "w"))
    item_list = [Item(int(v), int(w)) for v, w in items]
    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    print((solve_2()))

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
4 5
4 2
5 2
2 1
8 3
output:
13
"""
import sys
from collections import namedtuple


def solve():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        # for cp in range(real_cp - w, -1, -1):
        #     dp[cp + w] = max(dp[cp + w], dp[cp] + v)
        for cp in range(real_cp, w - 1, -1):
            dp[cp] = max(dp[cp], dp[cp - w] + v)
    return dp[-1]


if __name__ == "__main__":
    _input = sys.stdin.readlines()
    c_items, real_cp = list(map(int, _input[0].split()))
    items = [x.split() for x in _input[1:]]
    Item = namedtuple("Item", ("v", "w"))
    item_list = [Item(int(v), int(w)) for v, w in items]
    print((solve()))

-# def solve(): -#     for i, item in enumerate(item_list, 1): -#         for cp in range(1, real_cp + 1): -#             # capacity allows putting in, calculate value -#             if item.w <= cp: -#                 values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v) -#             # can't put in, skip current item -#             else: -#                 values[i][cp] = values[i - 1][cp] -# -#     return values[c_items][real_cp] -def solve_2(): + +def solve(): -        for cp in range(real_cp - w, -1, -1): -            dp[cp + w] = max(dp[cp + w], dp[cp] + v) +        # for cp in range(real_cp - w, -1, -1): +        #     dp[cp + w] = max(dp[cp + w], dp[cp] + v) +        for cp in range(real_cp, w - 1, -1): +            dp[cp] = max(dp[cp], dp[cp - w] + v) -    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)] -    print((solve_2())) +    print((solve()))