#include <iostream>
#include <fstream>
#define N_MAX 5000
#define G_MAX 10010

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");

long long int P[2][G_MAX], w[N_MAX], p[N_MAX], N, G;

int main()
{
    in >> N >> G;
    for(int i = 1; i <= N; i++)
        in >> w[i] >> p[i];

    /*for(int i = 1; i <= G; i++)
        if(w[1] <= i) P[1][i] = p[1];*/
        int i;
    for(i = 1; i <= N; i++)
    {
        for(int j = 0; j <= G; j++)
        {
            if(p[i] + P[!(i%2)][j] >= P[!(i%2)][w[i] + j])
            {   if(w[i] + j <= G) P[i%2][w[i] + j] = p[i] + P[!(i%2)][j]; }
            else if(w[i] + j <= G) P[i%2][w[i] + j] = P[!(i%2)][w[i] + j];

            if(P[i%2][j] < P[!(i%2)][j]) P[i%2][j] = P[!(i%2)][j];
        }
        /*for(int j = 3900; j <= G; j++)
            out << P[i%2][j] <<" ";
        out << endl;*/
    }
    /*for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j <= G; j++)
            out << P[i][j] << " ";
        out << endl;
    }*/
    out << P[(i-1)%2][G];
    return 0;
}