#include <fstream>

#define Max_Size 5009
#define Max_W 10009

using namespace std;

const char iname[] = "rucsac.in";
const char oname[] = "rucsac.out";

int N, G, DP[Max_W];

pair < int ,int >   V[Max_Size];

int main()
{
    ifstream in( iname );

    in >> N >> G;
    for(int i = 1; i <= N; ++i)
        in >> V[i].first >> V[i].second;

    for(int i = 1; i <= N; ++i)
        for(int j = G - V[i].first; j >= 0; --j)
            if(DP[ j + V[i].first ] < DP[j] + V[i].second)  DP[ j + V[i].first ] = DP[j] + V[i].second;

    int sol = 0;
    for(int i = 0; i <= G; ++i)
        sol = max( sol, DP[i] );

    ofstream out (oname);

    out << sol << '\n';
}