#include<fstream>
int max(int a,int b){ return a>b?a:b; }
using namespace std;
typedef struct pair { int g,p; }pr;
pr a[5005];
int b[10005],c[10005];
int main(void){
     ifstream fin("rucsac.in");
     ofstream fout("rucsac.out");
     int n,g,i,j;
     fin>>n>>g;
     for(i=1;i<=n;++i)fin>>a[i].g>>a[i].p; fin.close();
     
     for(i=1;i<=n;++i)
                if(i&1)       
                  for(j=1;j<=g;++j)
                    if(j-a[i].g>=0)b[j]=max(c[j],c[j-a[i].g]+a[i].p);       
                      else b[j]=c[j];                                              
                else       
                  for(j=1;j<=g;++j)
                    if(j-a[i].g>=0)c[j]=max(b[j],b[j-a[i].g]+a[i].p);       
                      else c[j]=b[j]; 
                    
     if(n&1)fout<<b[g]; else fout<<c[g];               
 return 0;   
}