#include <bits/stdc++.h>

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

int g[5005],p[5005],lin1[10005],lin2[10005],n,G,i,j;

int main()
{
    fin>>n>>G;
    for(i=1; i<=n; ++i)
        fin>>g[i]>>p[i];
    for(i=1; i<=n; ++i)
    {
        if(i%2==1)
            for(j=1; j<=G; ++j)
                if(j>=g[i])
                    lin2[j]=max(lin1[j],lin1[j-g[i]]+p[i]);
                else
                    lin2[j]=lin1[j];
        else if(i%2==0)
            for(j=1; j<=G; ++j)
                if(j>=g[i])
                    lin1[j]=max(lin2[j],lin2[j-g[i]]+p[i]);
                else
                    lin1[j]=lin2[j];
    }
    fout<<max(lin1[G],lin2[G]);

    return 0;
}