import sys

input=sys.stdin.readline



n, cap = list(map(int, input().split()))

val =[0]*(cap+1)

def nap(n,cap):

    for _ in range(n):

        w, v = list(map(int, input().split()))

        for wk in range(cap,w-1,-1):

            nv=val[wk-w]+v

            if val[wk]<nv:

                val[wk]=nv

    return max(val)

print((nap(n,cap)))

import sys



input = sys.stdin.readline





def nap(n, cap):

    val = [0] * (cap + 1)

    for _ in range(n):

        w, v = list(map(int, input().split()))

        for wk in range(cap, w - 1, -1):

            nv = val[wk - w] + v

            if val[wk] < nv:

                val[wk] = nv

    return max(val)





n, cap = list(map(int, input().split()))

print((nap(n, cap)))

import sys

input = sys.stdin.readline
n, cap = list(map(int, input().split()))
val = [0] * (cap + 1)


def nap(n, cap):
    for _ in range(n):
        w, v = list(map(int, input().split()))
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


print((nap(n, cap)))

import sys

input = sys.stdin.readline


def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = list(map(int, input().split()))
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = list(map(int, input().split()))
print((nap(n, cap)))

-n, cap = list(map(int, input().split())) -val = [0] * (cap + 1) +    val = [0] * (cap + 1) +n, cap = list(map(int, input().split()))