#include <fstream>

using namespace std;
int N, G, v[5001], g[5001], x[10000], vmax=0;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int dinamica()
{
    int i,j;
    x[0] = 0;
    for( i = 1; i <= G; i++)
        x[i] = -1;
    for(i = 1; i <= N; i++ )
        for( j = G - g[i]; j >= 0; j-- )
        if(x[j] != -1 && x[j] + v[i] > x[j + g[i]])
            {
                x[j+g[i]]=x[j]+v[i];
                if(x[ j + g[i]] > vmax) vmax = x[ j + g[i]];
            }
    return vmax;
}
int main()
{
    int i;
    fin>> N>> G;
    for( i = 1; i <= N; i++)
        fin>> g[i]>> v[i];
    fout<<dinamica();
    return 0;
}