#include <fstream>

using namespace std;

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

const int N = 5001;
const int G = 10001;

int w[N], p[N], d[G];

int main()
{
    int n, g, nrmax = 0;
    register int i;
    register int j;
    in >> n >> g;
    for ( i = 1; i <= n; i++ )
        in >> w[i] >> p[i];
    for ( i = 1; i <= n; i++ )
        for ( j = g - w[i]; j >= 0; j-- )
        {
            d[ j + w[i] ] = max( d[ j + w[i] ], d[j] + p[i] );
        }
    for ( i = 0; i <= g; i++ )
        if ( nrmax < d[i] )
            nrmax = d[i];
    out << nrmax;
    return 0;
}