#include <fstream>
using namespace std;

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

const int Nmax = 5001;
const int Gmax = 10001;

int n, g;
int P[Nmax], W[Nmax];
int Profit[Gmax];

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 ( Profit[j + W[i]] < Profit[j] + P[i] )
                Profit[j + W[i]] = Profit[j] + P[i];
    os << Profit[g];

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