#include <fstream>
using namespace std;

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

long long l[10050], maxim;
int i, j, valoare, greu, nr, greutate;

int main()
{
    fin >> nr >> greutate;

    l[0] = 1;

    for(i=1; i <= nr; i++)
    {
        fin >> greu >> valoare;
        for(j=greutate; j >= greu; j--)
        {
            if(l[j-greu] != 0)
            {
                l[j] = max(l[j], l[j-greu]+valoare);
            }
        }
    }
    for(i=1; i <= greutate; i++)
    {
        maxim=max(maxim, l[i]-1);
    }
    fout << maxim;
}