#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int main(){
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n, g;
    cin>>n>>g;
    int w[n],v[n],dp[n+1][g+1];
    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]]);
     }
     
    /*for(int i=0;i<=n;i++){
    for(int j=0;j<=g;j++)cout<<dp[i][j]<<' ';
    cout<<'\n';
    }*/
     
    cout<<dp[n][g];
}