#include <iostream>
#include<fstream>
using namespace std;
int d[5005][10005],n,m,i,j,g,p[5005],w[5005],y,x;
int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in>>n>>g;
    for(i=1;i<=n;i++)
    {
        in>>w[i]>>p[i];
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=g;j++)
        {
            if(i%2==0)
            {
                if((j-w[i])<0)
                {
                    y=0;
                    x=0;
                }
                else
                {
                    y=j-w[i];
                    x=p[i];
                }
                d[2][j]=max(d[1][j], d[1][y]+x);
            }
            else
            {
                if((j-w[i])<0)
                {
                    y=0;
                    x=0;
                }
                else
                {
                    y=j-w[i];
                    x=p[i];
                }
                d[1][j]=max(d[2][j], d[2][y]+x);
            }

        }
    }
     int s=max(d[1][g],d[2][g]);
     out<<s;
}