#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;
    for(int i = 1 ; i <= n ; ++ i){
        fin >> w >> p;
        l += w;
        for(int j = l ; j >= 0 ; -- j){
            if(!j || (dp[j] && j + w <= g && dp[j] + p > dp[j + w])){
                dp[j + w] = dp[j] + p;
            }
        }
    }
    fout << dp[g] << '\n';
    return 0;
}