#include <fstream>

using namespace std;

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

const int N = 5005;
const int G = 10005;

int w[N], p[N];
int n, g;
int d[2][G];

inline int maxim (int a, int b)
{
    if (a > b)
        return a;
    return b;
}

int main()
{
    in >> n >> g;

    for (int i = 1; i <= n; i++) {
        in >> w[i] >> p[i];
    }

    int linie = 0;

    for (int i = 1; i <= n; i++, linie = 1 - linie) {
        for (int cw = 0; cw <= g; cw++) {
            d[1-linie][cw] = d[linie][cw];

            if(w[i] <= cw) {
                d[1-linie][cw] = maxim(d[1-linie][cw], d[linie][cw - w[i]] + p[i]);
            }
        }
    }

    out << d[linie][g] << "\n";

    return 0;
}