#include<fstream>
using namespace std;
unsigned greutate[5001],profit[5000],optim[10001];
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int i,j,N,G;
    f>>N>>G;
    for(i=1;i<=N;i++)
        f>>greutate[i]>>profit[i];
    for(i=1;i<=N;i++)
        for(j=G-greutate[i];j>=0;j--)
            if(optim[j+greutate[i]]<optim[j]+profit[i])
                optim[j+greutate[i]]=optim[j]+profit[i];
    g<<optim[G];
    return 0;
}