#include <fstream>

using namespace std;

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

int n , g;
int w[5005] , v[5005] , sol[2][10005];

int main()
{
    fin >> n >> g;
    for(int i = 1 ; i <= n ; ++i) fin >> w[i] >> v[i];

    int l = 1;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 0 ; j <= g ; ++j){
            sol[1-l][j] = sol[l][j];
            if(w[i] <= j) sol[1-l][j] = max(sol[l-1][j] , sol[l][j - w[i]] + v[i]);
        }
        l = 1 - l;
    }
    fout << sol[l][g];

    return 0;
}