#!/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]





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)]

    ans = solve()

    print(ans)
#!/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)]

    ans = solve_2()

    print(ans)
#!/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]


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)]
    ans = solve()
    print(ans)

#!/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)]
    ans = solve_2()
    print(ans)

- -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(): +#     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] -    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)] -    ans = solve() +    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)] +    ans = solve_2()