#include <fstream>
#include <algorithm>

using namespace std;

ifstream in ("rucsac.in");
ofstream out ("rucsac.out");

#define MAXN 5001
#define MAXG 10001

int Profit[2][MAXG], N, G, W[MAXN], P[MAXN];

int main()
{
    int i, cw, L;
    in >> N >> G;
    for (i = 1; i <= N; i++) in >> W[i] >> P[i];
    L = 1;
    for (i = 1; i <= N; i++, L = 1 - L)
    {
        for (cw = 1; cw <= G; cw++)
        {
            Profit[L][cw] = Profit[1 - L][cw]; // pentru inceput nu includ obiectul i in submultime
            if (W[i] <= cw) Profit[L][cw] = max (Profit[L][cw], Profit[1 - L][cw - W[i]] + P[i]); // verific daca pot mari profitul
        }
    }
    out << Profit[1 - L][G];
    return 0;
}