#include <fstream>

#define dL 10001

using namespace std;

ifstream in;
ofstream out;

int d[dL];

int main()
{
    int N,G,g,c;

    in.open("rucsac.in");

    in>>N>>G;

    int max=0;
    for(;N--;)
    {
        in>>g>>c;

        for(int i=max;i>=0;--i)
            if(d[i]>=0)
                if(i+g<=G)
                {
                    if(d[i+g]<0||d[i+g]<d[i]+c)
                        d[i+g]=d[i]+c;
                    if(max<i+g) max=i+g;
                }

    }

    in.close();

    out.open("rucsac.out");

    out<<d[max]<<'\n';

    out.close();

    return 0;
}