#include <fstream>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

int V[10014],N;
int G,Gmax,Gr,Va;

inline int _max(int a,int b){if(a>b)return a;return b;}

int main()
{
    int i,gr;
    in>>N>>G;
    V[0]=1;
    for(i=1;i<=N;i++)
    {
        in>>Gr>>Va;
        //iau toate greutatile anterioare si vad daca pot face o valoare mai mare
        for(gr=Gmax;gr>=0;--gr)
        {
            if(!V[gr])continue;//nu am putut forma
            if(gr+Gr<=G)
                V[gr+Gr]=_max(V[gr+Gr],V[gr]+Va);
        }
        if(Gr+Gmax>G)
            Gmax=G;
        else Gmax+=Gr;

    }
    in.close();
    for(gr=G,Va=0;gr>=0;--gr)
        Va=_max(Va,V[gr]);
    out<<Va-1<<'\n';
    out.close();
    return 0;
}