#include <fstream>
#include <string.h>

using namespace std;

unsigned long rucsac(const int *p, const int *w, const int n, const int G) {
    int i, j;
    unsigned long prev[G + 1], current[G + 1];
    for (i = 0; i <= G; i++)
        prev[i] = current[i] = 0UL;

    for (i = 1; i <= n; i++) {
        for (j = 0; j <= G; j++) {
            current[j] = prev[j];

            if (j >= w[i - 1]) {
                unsigned long priceWithThisObj = prev[j - w[i - 1]] + p[i - 1];
                if (priceWithThisObj > current[j]) {
                    current[j] = priceWithThisObj;
                }
            }
        }
        memcpy(prev, current, (G + 1) * sizeof(*prev));
    }

    return current[G];
}

int main(void) {
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    int i, n, G;
    in >> n >> G;
    int p[n], w[n];

    for (i = 0; i < n; i++)
        in >> w[i] >> p[i];

    out << rucsac(p, w, n, G);

    in.close();
    out.close();
    return 0;
}