#include<iostream>
#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gr[5001],val[5001];
long v1[10001],v2[10001],G;
int maxim(long a,long b)
{
    if (a>b)return a;
    return b;
}
int main()
{
    int i,ok=1;
    long j;
    f>>n>>G;
    for(i=1;i<=n;i++)
       f>>gr[i]>>val[i];
    for(i=1;i<=n;i++)
        {
            if(ok)
                {
                    for(j=1;j<=G;j++)
                       if(gr[i]>j)
                           v2[j]=v1[j];
                        else
                           v2[j]=maxim(v1[j],v1[j-gr[i]]+val[i]);
                        ok=0;


                }
            else
               {
                  for(j=1;j<=G;j++)
                       if(gr[i]>j)
                           v1[j]=v2[j];
                        else
                           v1[j]=maxim(v2[j],v2[j-gr[i]]+val[i]);
                        ok=1;


               }
        }
    if(n%2==0)g<<v1[G];
    else g<<v2[G];
    f.close();
    g.close();
    return 0;
}