#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");
short int n,g;
vector<pair<short int,short int> > ob;
int *pr;
int best = 0;

int main()
{
    in>>n>>g;
    int x,y;
    for(int i=1;i<=n;i++)
    {
        in>>x>>y;
        ob.push_back(make_pair(x,y));
    }
    in.close();
    pr = new int[g+1];
    for(int i=0;i<=g;i++)
        pr[i] = 0;
    int maxx = 0;
    for(unsigned int i=0;i<ob.size();i++)
        for(int j = maxx;j>=0;j--)
            if((pr[j] || j==0) && (j+ob[i].first <= g) && (pr[j+ob[i].first] < pr[j] + ob[i].second))
            {
                pr[j+ob[i].first] = pr[j] + ob[i].second;
                if(best < pr[j+ob[i].first])
                    best = pr[j+ob[i].first];
                if(maxx < j+ob[i].first)
                    maxx = j+ob[i].first;
            }
    out<<best<<"\n";
    out.close();
    delete[] pr;
    return 0;
}