#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
    int n, g;
    fin >> n >> g;
    vector <int> v(n + 1), w(n + 1);
    for(int i = 1; i <= n; ++i){
        fin >> w[i] >> v[i];
    }
    int line = 0;
    vector <vector <int>> d(2, vector <int>(g + 1));
    for(int i = 1; i <= n; ++i, line = (line + 1) % 2){
        for(int j = 1; j <= g; ++j){
            int case1 = d[(line + 1) % 2][j];
            int case2 = 0;
            if(j >= w[i]) case2 = v[i] + d[(line + 1) % 2][j - w[i]];
            d[line][j] = max(case1, case2);
        }
    }
    fout << d[(line + 1) % 2][g];
    return 0;
}