#include <fstream>
using namespace std;

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

int N, G, v[5001], g[5001];
int sol;
int D[10005];

int main()
{
    is >> N >> G;
    for (int i = 1; i <= N; ++i)
        is >> g[i] >> v[i];
    for (int i = 1; i <= G; ++i)
        D[i] = -1;
    for (int i = 1; i <= N; ++i)
        for (int j = G-g[i]; j >= 0; --j)
            if (D[j] >= 0)
                D[j+g[i]] = max(D[j] + v[i], D[j+g[i]]), sol = max(D[j+g[i]], sol);
    os << sol;
    is.close();
    os.close();
}