#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n,gmax,i,j,p[5001],g[5001],sol[3][10001];
int main()
{
    in>>n>>gmax;
    for (i=1; i<=n; ++i)
    {
        in>>g[i]>>p[i];
    }
    for (i=1; i<=n; ++i)
    {
        if (i>1)
        {
            for (j=1; j<=gmax; ++j)
            {
                if (g[i]>j)
                    sol[2][j]=sol[1][j];
                else
                    sol[2][j]=max(sol[1][j],sol[1][j-g[i]]+p[i]);
            }
            if (i!=gmax)
            {
                for (j=1; j<=gmax; ++j)
                    sol[1][j]=sol[2][j];
            }
        }
        else
        {
            for (j=1; j<=gmax; ++j)
            {
                if (g[i]>j)
                    sol[1][j]=sol[0][j];
                else
                    sol[1][j]=max(sol[0][j],sol[0][j-g[i]]+p[i]);
            }
        }
    }
    out<<sol[2][gmax]<<"\n";
}