#include <fstream>

using namespace std;

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

int pret[5010],greutate[5010],tabel[3][10010],n,grmax,i,j,lat=1;

int main()
{
    fin>>n>>grmax;
    for(i=1;i<=n;++i)
    {
        fin>>greutate[i]>>pret[i];
    }

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

            if(greutate[i]<=j)
            {
                tabel[lat][j]=max(tabel[1-lat][j],tabel[1-lat][j-greutate[i]]+pret[i]);
            }
        }
    }
    fout<<tabel[lat][grmax];
    return 0;
}