#include<fstream>
using namespace std;
ifstream F("rucsac.in");
ofstream G("rucsac.out");
int g[5001],c[5001],s[10001],m,n,i,j,t;
int main()
{
    F>>n>>m;
    for(i=1;i<=n;++i)
        F>>g[i]>>c[i];
    for(i=1;i<=n;++i)
        for(j=m-g[i];j>=0;--j)
        	if(s[j+g[i]]<s[j]+c[i])
            	s[j+g[i]]=s[j]+c[i],t=s[j+g[i]]>t?s[j+g[i]]:t;
    G<<t;
    return 0;
}