#include <fstream>
#include <vector>

using namespace std;

struct Obiect
{
    int w, p;
    friend istream& operator>>(istream &in, Obiect &o)
    {
        return in >> o.w >> o.p;
    }
    friend ostream& operator<<(ostream &out, Obiect &o)
    {
        return out << o.w << ' ' << o.p;
    }
};

int d[2][10001];
int main()
{
    ifstream fin("rucsac.in");
    int n, g;
    fin >> n >> g;
    vector<Obiect> obiecte(n);
    for(Obiect &o: obiecte)
        fin >> o;
    int l=0;
    for(int i=1; i<=n; ++i, l=1-l)
        for(int cw=0; cw<=g; ++cw)
        {
            d[1-l][cw] = d[l][cw];
            if(obiecte[i-1].w <= cw)
                d[1-l][cw] = max(d[1-l][cw], d[l][cw - obiecte[i-1].w] + obiecte[i-1].p);
        }
    ofstream fout("rucsac.out");
    fout << d[l][g];
    return 0;
}