#include <fstream>
#include <vector>
using namespace std;

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

int max(int x, int y) {
    return (x > y) ? x : y;
}

int main() {
    int n, g;
    fin >> n;
    fin >> g;

    vector<int> w(n); 
    vector<int> p(n);

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

    vector<vector<int> > m(n + 1, vector<int> (g + 1));

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= g; ++j) {
            if (j == 0 || i == 0) {
                m[i][j] = 0;
            } else if (w[i - 1] <= j) {
                m[i][j] = max(m[i - 1][j], p[i - 1] + m[i - 1][j - w[i - 1]]);
            } else {
                m[i][j] = m[i - 1][j];
            }
        }
    }

    fout << m[n][g];

    return 0;
}