#include <fstream>

using namespace std;

int n, g, w[5001], p[5001], op[10001], ma;

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

    fin >> n >> g;

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

    for(int i = 1; i <= n; ++i)
        for(int j = g - w[i]; j >= 0; --j)
            if(op[j + w[i]] < op[j] + p[i])
            {
                op[j + w[i]] = op[j] + p[i];
                if(op[j + w[i]] > ma)
                    ma = op[j + w[i]];
            }

    fout << ma;

    return 0;
}