#include <fstream>
#include <algorithm>

using namespace std;

const int Gmax=10005;
const int Nmax=5005;

int cmax[Gmax];
bool used[Gmax][Nmax];

struct obiect {
    int w,p;
} v[Nmax];

bool cmp(obiect i1, obiect i2) {
    if (i1.p==i2.p) {
        return i1.w<i2.w;
    }
    return i1.p>i2.p;
}

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int n,g;
    fin>>n>>g;
    for (int i=1; i<=n; ++i) {
        fin>>v[i].w>>v[i].p;
    }
    /*for (int i=1; i<=n; ++i) {
        fout<<v[i].p<<' ';
    }
    fout<<endl;

    for (int i=1; i<=n; ++i) {
        fout<<v[i].w<<' ';
    }
    fout<<endl;*/
    for (int s=1; s<=g; ++s) {
        int ll=s-1,poz=s-1;
        cmax[s]=cmax[s-1];
        for (int i=1; i<=n; ++i) {
            if (v[i].w<=s && used[s-v[i].w][i]==0 && cmax[s]<cmax[s-v[i].w]+v[i].p) {
                used[s][i]=1;
                cmax[s]=cmax[s-v[i].w]+v[i].p;
                ll=s-v[i].w;
                poz=i;
                //fout<<s<<' '<<cmax[s]<<' '<<v[i].w<<' '<<v[i].p<<endl;
            }
        }
        for (int i=1; i<=n; ++i) {
            if (i!=poz) {
                used[s][i]=0;
            }
        }
        for (int i=1; i<=n; ++i) {
            used[s][i]=max(used[s][i],used[ll][i]);
        }
        //fout<<endl;
    }
    /*for (int i=1; i<=g; ++i) {
        for (int j=1; j<=n; ++j) {
            fout<<used[i][j]<<' ';
        }
        fout<<endl;
    }
    for (int i=1; i<=g; ++i) {
        fout<<cmax[i]<<' ';
    }
    fout<<endl;*/
    fout<<cmax[g];
    fin.close();
    fout.close();
    return 0;
}