#include <fstream>

using namespace std;

int n, g;
int w[5001], p[5001];
long v[5001];

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

int rucsac ()
{
    int i, j;
    for(i=1; i<=n; i++)
        for(j=g; j>=w[i]; j--)
            v[j] = max(v[j], v[j- w[i]] + p[i]);
    return v[g];
}
int main()
{
    int i;
    fin>>n>>g;
    for(i=1; i<=n; i++)
        fin>>w[i]>>p[i];
    fin.close();
    fout<<rucsac();
    fout.close();
    return 0;
}