#include<algorithm>
#include<fstream>
#include<cassert>
#include<vector>

#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int dp[10001];
int main(){
    int n , g , w , p , l;
    fin >> n >> g;
    fin >> w >> dp[w];
    l = w;
    for(int i = 1 ; i < n ; ++ i){
        fin >> w >> p;
        for(int j = l ; j >= 0 ; -- j){
            if(dp[j] && j + w <= g)
                dp[j + w] = max(dp[j + w] , dp[j] + p);
        }
        dp[w] = max(dp[w] , p);
        l = min(g , l + w);
    }
    fout << *max_element(dp + 1 , dp + 1 + g) << '\n';
    return 0;
}