#include <fstream>

using namespace std;
const int MAX=5e3+14;
const int MAX2=1e4+14;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int vg[MAX];
int vp[MAX];
int rep[MAX2];
int main()
{
    int n,g,i,j=1,max=0;
    fin>>n>>g;
    for(int i=1;i<=n;i++)
    {
        fin>>vg[i]>>vp[i];
    }

    for(i=1;i<=n;i++)
        for(j=g-vg[i];j>=0;--j)
            if(rep[j+vg[i]]<rep[j]+vp[i])
            {
                rep[j+vg[i]]=rep[j]+vp[i];
                if(max<rep[j+vg[i]])max=rep[j+vg[i]];
            }
    fout<<max;

    return 0;
}