#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int nmax = 5005;
const int gmax = 10005;
int N, G, w[nmax], p[nmax], op[gmax], sol;
int main()
{
    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];
                sol = max(sol, op[j + w[i]]);
            }
    fout << sol;
}