#include <fstream>
using namespace std;

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

int w[5005],p[5005],n,gr,i,j;
int c1[10005],c2[10005];

int main()
{
    f>>n>>gr;
    for(i=1;i<=n;i++)
        f>>w[i]>>p[i];

    for(i=1;i<=n;i++)
    {
        for(j=0;j<=gr;j++)
        {
            if(i%2==1)
            {
                c2[j]=c1[j];
                if(w[i]<=j)
                    c2[j]=max(c1[j], c1[j-w[i]]+p[i]);
            }
            else
            {
                c1[j]=c2[j];
                if(w[i]<=j)
                    c1[j]=max(c2[j], c2[j-w[i]]+p[i]);
            }

        }
    }
    /*
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=gr;j++)
                g<<cost[i][j]<<' ';
            g<<'\n';
        }
    */

    if(n%2==1)
        g<<c2[gr];
    else g<<c1[gr];

    return 0;
}