#include <fstream>

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

int N,G,k,i,j,a[10005],b[10005];
struct pachet{int g,v;}p[5005];

int main()
{

    fin>>N>>G;
    for(k=1;k<=N;++k) fin>>p[k].g>>p[k].v;
    for(j=p[1].g;j<=G;++j) a[j]=p[1].v;
    for(i=2;i<=N;++i)
    {
        if(i&1)
        {
             for(j=1;j<=G;++j)
                a[j]=max(b[j],b[j-p[i].g]+p[i].v);
        }
        else
        {
            for(j=1;j<=G;++j)
                b[j]=max(a[j],a[j-p[i].g]+p[i].v);

        }
    }
    if(G&1) fout<<a[G];
    else fout<<b[G];
    return 0;
}