// Galatan Tudor - Ion Luca Theoretical High School
// Husi, Romania, Su, August 30, 2015

#include <algorithm>
#include <cstring>
#include <fstream>
#include <vector>
 
#define Max_No 5001
#define Max_Wgt 10001
  
using namespace std;
 
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
 
int w[Max_No], p[Max_No];
int OV[Max_Wgt];
int N, G, i, sol, j;

int main () 
{
    in >> N >> G;
        for (i=1; i<=N; i++)
            in >> w[i] >> p[i];
        OV[0] = 0;
        sol = 0;
    for (i=1; i<=N; i++)
            for (j=G-w[i]; j>=0; j--)
        {
            if (OV[j+w[i]] < OV[j]+p[i])
            {
                OV[j+w[i]] = OV[j]+p[i];
                if (OV[j+w[i]] > sol)
                    sol = OV[j+w[i]];
            }
        }
    out << sol;
    return 0;
}