#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=1;i<=n;i++){
    for(int j=0;j<=g;j++)dp[0][j]=dp[1][j];
    for(int j=0;j<=g;j++)dp[1][j]=max(dp[0][j],v[i]+dp[0][j-w[i]]);
     }  
    cout<<dp[1][g];
}