#include <fstream>

using namespace std;

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

int n,m,w[5001],p[5001],optim[10001];

int main(){
    int i,j;
    f>>n>>m;
    for(i=1; i<=n; i++)
        f>>w[i]>>p[i];

    int sol=0;
    optim[0]=0;
    for(i=1; i<=n; i++){
        for(j=m-w[i];j>=0;j--)
            if( optim[j+w[i]] < optim[j]+p[i] )
			{
				optim[j+w[i]] = optim[j] + p[i];
				if( optim[j+w[i]] > sol)
					sol = optim[j+w[i]];
			}
			/*for(j=0; j<=m; j++)
                g<<optim[j]<<" ";
            g<<"\n";*/
		}

     g<<sol;

    return 0;
}