#include <fstream>

using namespace std;

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

int i,n,grmax,pr[5011],j,gr[5010],tabel[3][10010],lat=1;


int main()
{
    fin>>n>>grmax;
    for(i=1;i<=n;++i)
    {
        fin>>gr[i]>>pr[i];

    }

    for(i=1;i<=n;++i)
    {
        lat=1-lat;

        for(j=0;j<=grmax;++j)
        {
            //tabel[lat][j]=tabel[1-lat][j];

            if(gr[i]<=j)
            {
                tabel[lat][j]=max(tabel[1-lat][j] , pr[i]+ tabel[1-lat][j-gr[i]]);
            }
        }

    }

    fout<<tabel[lat][grmax];
    return 0;
}