#include <fstream>
using namespace std;

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

int nr, greutate, i, j, l1[5005], l2[5005], valoare, greu,maxim;

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

    l1[0] = 1;
    l2[0] = 1;

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