#include <fstream>
using namespace std;

#define MaxN 5001
#define MaxG 10001

ifstream is("rucsac.in");
ofstream os("rucsac.out");

int p[MaxN], w[MaxN];
int knp[MaxG];
int n, g, sol;

int main()
{
    is >> n >> g;
    for ( int i = 1; i <= n; ++i )
        is >> w[i] >> p[i];

    for ( int i = 1; i <= n; ++i )
        for ( int j = g - w[i]; j >= 0; --j )
            if ( knp[j + w[i]] < knp[j] + p[i] )
            {
                knp[j + w[i]] = knp[j] + p[i];
                sol = max(sol, knp[j + w[i]]);
            }

    os << sol;

    is.close();
    os.close();
    return 0;
}