#include <fstream>

using namespace std;

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

struct object
{
    int gre;
    int val;
}item[5000];

int D[3][10001],N,i,j,G;

int main()
{
    fin>>N>>G;
    for (i=1;i<=N;i++)
        fin>>item[i].gre>>item[i].val;
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=G;j++)
        {
            if (item[i].gre>j) D[2][j] = D[1][j];
            if (item[i].gre==j) D[2][j] = max(D[1][j], item[i].val);
            if (item[i].gre<j) D[2][j] = max(D[1][j],item[i].val+D[1][j-item[i].gre]);
        }
        for (j=1;j<=G;j++)
            D[1][j] = D[2][j];
    }

    fout<<D[1][G];
    return 0;
}