#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int const G = 10001;
int n , g;
int wi , pi;
int dp[G];
int main()
{
    fin >> n >> g;
    dp[0] = 1;
    int gmax = 0;
    for(int i = 1 ; i <= n ; ++ i){
        fin >> wi >> pi;
        for(int j = gmax ; j >= 0 ; -- j){
            if(j + wi <= g && dp[j]){
                dp[j + wi] = max(dp[j + wi] , dp[j] + pi);
                gmax = max(gmax , j + wi);
            }
        }
    }
    fout << dp[g] - 1 << '\n';
    return 0;
}