#include <bits/stdc++.h>
using namespace std;
int i,n,g,j,w[10002],p[10002],dp[5002][10002];
int main(){
    ifstream cin ("rucsac.in");
    ofstream cout ("rucsac.out");
    cin>>n>>g;
    for (i=1;i<=n;i++)
     cin>>w[i]>>p[i];
    for (i=1;i<=n;i++)
     for (j=1;j<=g;j++){
      if(j-w[i]<0) dp[i][j]=dp[i-1][j];
        else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
     }
 
cout<<dp[n][g];
    return 0;
}