#include <fstream>
#include <cmath>

using namespace std;

    int v[10005];
    int n,g;
    int i,w[5000],p[5000];
int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

    fin>>n>>g;
    for(i=0;i<n;i++)
        fin>>w[i]>>p[i];
    int j;
    for(i=0;i<n;i++)
        for(j=g;j>=0;j--)
            if(w[i]<=j)
                v[j]=max(v[j],v[j-w[i]]+p[i]);
    fout<<v[g]<<'\n';
    fin.close();
    return 0;
}