#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
#define nmax 5001
#define gmax 10001
int w[nmax], p[nmax], n, G, gr[gmax], v[gmax];
int main()
{
    f >> n >> G;
    for (int i = 1; i <= n; ++i) f >> w[i] >> p[i];
    for (int i = 1; i <= n; ++i) {
        int j;
        for (j = G; j > w[i]; --j)
            if (gr[j - w[i]])
                if (v[j - w[i]] + p[i] > v[j]) {
                    v[j] = v[j - w[i]] + p[i];
                    gr[j] = i;
                }
        if (p[i] > v[j]) {
            v[j] = p[i];
            gr[j] = i;
        }
    }
    int maxi = 0;
    for (int i = 1; i <= G; ++i) maxi = max(maxi,v[i]);
    g << maxi << endl;
    return 0;
}