#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");


int weights[10001], prices[10001],v1[10001],v2[10002];
int *p=v1, *q=v2, *aux;




int backpack (int C, int n)
{
int i,j,w;
for(i=1;i<=n;i++)
    {
        for(w=1;w<=C;w++)
        if(weights[i]<=w)
        p[w]=max(q[w],prices[i]+q[w-weights[i]]);
        else p[w]=q[w];
        aux=p;p=q;q=aux;





    }
if(n%2==0) return q[C];
else return p[C];


}

int main()
{
int i,n,c,j;
f>>n>>c;
for(i=1;i<=n;i++)
    f>>weights[i]>>prices[i];
    g<<backpack(c,n);

}