#include <fstream>

using namespace std;

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

    for (i = 0; i <= G; i++)
        res[0][i] = 0UL;

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

            if (j >= w[i - 1]) {
                unsigned long priceWithThisObj = res[i - 1][j - w[i - 1]]
                    + p[i - 1];
                if (priceWithThisObj > res[i - 1][j]) {
                    res[i][j] = priceWithThisObj;
                }
            }
        }
    }

    unsigned long maxProfit = res[n][G];
    for (i = 0; i <= n; i++)
        delete[] res[i];
    delete[] res;

    return maxProfit;
}

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;
}