#include <cstdio>
 #include <algorithm>
 #define G 10010
 #define N 5010
 using namespace std;
  
int sol[G],value[N],weight[N],n,w; 

 void read() 
{  
   scanf("%d %d",&n,&w);
  
   for(int i=1;i<=n;i++) 
        scanf("%d %d",&weight[i],&value[i]);  
      
 }  


 void solve()
 {     for(int i=1;i<=n;i++)  
           for(int j=w;j-weight[i]>=0;j--)    
                 sol[j]=max(sol[j],sol[j-weight[i]]+value[i]);    
        
 }  

 void write()
 {     
   printf("%d",sol[w]);
 }

 int main()
 {
  freopen("rucsac.in","r",stdin);
  freopen(" rucsac.out","w",stdout); 

  read();   
  solve();
   write(); 
}