#include <fstream>

using namespace std;

int p[5010], w[5010];
int dp[10010];

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int main(){
    int n, g;
    f >> n >> g;
    int best = 0;

    for(int i = 1; i <= n; ++i){
        f >> w[i] >> p[i];
    }

    for(int i = 1; i <= n; ++i){
        for(int j = g-w[i]; j >= 0; --j){
            if(dp[j+w[i]] < dp[j] + p[i]){
                dp[j+w[i]] = dp[j] + p[i];
                best = max(best, dp[j+w[i]]);
            }
        }
    }

    g << best;
    return 0;
}