#include <iostream>
#include <fstream>
#define NMAX 5005
#define GMAX 10005
using namespace std;

int main() {
    int n, g;
    int w[NMAX], p[NMAX], d[GMAX];

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

    fin >> n >> g;
    for (int i = 0; i < n; ++i)
        fin >> w[i] >> p[i];
    for (int i = 0; i <= g; ++i)
        d[i] = 0;
    
    for (int i = 0; i < n; ++i)
        for (int j = g; j >= w[i]; --j)
            d[j] = max(d[j], d[j - w[i]] + p[i]);

    fout << d[g];

    return 0;
}