#include <iostream>
#include <fstream>

using namespace std;

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

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

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

    for (int l = 1; l <= length; ++l) {
        for (int c = 1; c <= gMax; ++c) {
            matrix[l][c] = matrix[l - 1][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';
    }

    cout << matrix[length][gMax];

    return 0;
}