#include <fstream>
#define DMAX 5010
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int GMAX, g[DMAX], p[DMAX], pmax[3][DMAX*2], n;
void citire(), pd();
int main()
{
    citire();
    pd();
    return 0;
}

void citire()
{
    fin>>n>>GMAX;
    int i;
    for (i=1; i<=n; ++i)
        fin>>g[i]>>p[i];
    return;
}

void pd()
{
    int i, G;
    for (G=1; G<=GMAX; ++G)
        if (g[1]<=G)
            pmax[0][G]=p[1];
    int lin=1;
    for (i=2; i<=n; ++i)
        for (G=1; G<=GMAX; ++G)
        {
            pmax[lin][G]=pmax[lin-1][G];
            if (g[i]<=G)
                if (p[i]+pmax[lin-1][G-g[i]]>pmax[lin][G])
                    pmax[lin][G]=p[i]+pmax[lin-1][G-g[i]];
            lin=1-lin;
        }
    fout<<pmax[n][GMAX]<<"\n";
    fout.close();
    return;
}