#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, G, w[5001], p[5001], gr[10001], v[10001];
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]) {
                    gr[j] = i;
                    v[j] = v[j-w[i]] + p[i];
                }
            }
        if (p[i] > v[j]) {
            gr[j] = i;
            v[j] = p[i];
        }
    }
    g << v[G] << endl;
    return 0;
}