#include <iostream>
#include <cstdio>
#include <algorithm>
  
using namespace std;
  
int w[5003],v[5003],dp[2][10003];
  
int main(){
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n, g;
    cin>>n>>g;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
      
    for(int i=0;i<=g;i++)dp[0][i]=0;
      
    for(int i=1;i<=n;i++)
    for(int j=0;j<=g;j++){
         dp[0][j]=dp[1][j];
         dp[1][j]=max(dp[0][j],v[i]+dp[0][j-w[i]]);
     }
      
    cout<<dp[n][1];
}