#include <iostream>
#include <fstream>

using namespace std;

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

int matrix[2][10005];
int g[10005], p[10005];
int length, gMax;

int main() {
    fin >> length >> gMax;
    for (int iter = 0; iter < length; ++iter) {
        fin >> g[iter] >> p[iter];
    }

    for (int l = 0; l < length; ++l) {
        for (int c = 0; c < gMax; ++c) {
            int actualLine = l % 2, otherLine = 1 - actualLine;
            matrix[actualLine][c] = matrix[otherLine][c];
            if (g[l] <= c)
                matrix[l][c] = max(matrix[l - 1][c], matrix[l - 1][c - g[l]] + p[l]);
        }
    }
//    for (int l = 1; l <= length; ++l) {
//        for (int c = 1; c <= gMax; ++c) {
//            fout<<matrix[l][c]<<'\t';
//        }
//        fout<<'\n';
//    }

    fout << matrix[length][gMax];

    return 0;
}