#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int NMAX = 5001;
const int INFI = 0x3f3f3f3f;
int Gmax, N;
int g[NMAX], p[NMAX];

int rucsac(int i, int Gramas){
    if(i == 0){
        return 0;
    }

    int profit_skip_obj = rucsac(i - 1, Gramas);

    int profit_luat_obj = 0;
    if(g[i] <= Gramas){
        profit_luat_obj = p[i] + rucsac(i - 1, Gramas - g[i]);
    }

    if(profit_skip_obj > profit_luat_obj){
        return profit_skip_obj;
    }
    return profit_luat_obj;
}



int main()
{
    fin >> N >> Gmax;
    for(int i = 1; i <= N; i++){
        fin >> g[i] >> p[i];
    }
    fout << rucsac(N, Gmax);
    return 0;
}