#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(); 
}