#include <fstream>

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

int g[10003], p[10003];
int ruc[2][5001];
int main()
{
    int n, i, G, ct;
    fin>>n>>G;
    for(int i=1;i<=n;i++)
        fin>>g[i]>>p[i];

    for(int x=1;x<=n;x++)
    {
        if(x%2!=0)
        {
            i=1;
            ct=-1;
        }
        else
        {
            i=0;
            ct=1;
        }
        for(int gc=1;gc<=G;gc++)
        {
            if(gc-g[x]>=0)
                ruc[i][gc]=max(ruc[i+ct][gc], ruc[i+ct][gc-g[x]]+p[x]);
            else
                ruc[i][gc]=ruc[i+ct][gc];
        }
    }

    if(n%2!=0)
        fout<<ruc[1][G];
    else
        fout<<ruc[0][G];
    return 0;
}