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