#include <fstream>

#define input "rucsac.in"
#define output "rucsac.out"
#define NMAX 5005
#define GMAX 10005

using namespace std;

ifstream in(input);
ofstream out(output);

int N, G, H[NMAX], P[NMAX], DP[2][GMAX];

void Read_Data()
{
    in >> N >> G;
    for(int i = 1; i <= N; i++)
        in >> H[i] >> P[i];
}

void Solve()
{
    int l, i, j;
    for(i = 1, l = 0; i <= N; i++, l = 1 - l)
        for(j = 0; j <= G; j++)
            if(j - H[i] >= 0) DP[l][j] = max(DP[1 - l][j], DP[1 - l][j - H[i]] + P[i]);
            else DP[l][j] = DP[1 - l][j];
    l = 1 - l;
    out << DP[l][G] << "\n";
}

int main()
{
    Read_Data();
    Solve();
    return 0;
}