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