#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int pd[2][10001],g[5001],p[5001];
int i,j,n,greutate,l;
int main()
{
    fin>>n>>greutate;
    for(i=1;i<=n;i++)
        fin>>g[i]>>p[i];
    l=0;
    for(i=1;i<=n;i++,l=1-l)
    {
        for(j=0;j<=greutate;j++)
        {
            pd[1-l][j]=pd[l][j];
            if(g[i]<=j&&pd[l][j-g[i]]+p[i]>pd[1-l][j])
                pd[1-l][j]=pd[l][j-g[i]]+p[i];
        }
    }
    fout<<pd[l][greutate];
    return 0;
}