#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

const int NMAX = 10000;

int p[NMAX], w[NMAX], d[NMAX][NMAX];
int n, g;

int main(){

    cin >> n >> g;
    for(int i = 1; i <= n; i++) {
        cin >> w[i] >> p[i];
    }

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

    cout << d[n][g] << "\n";
    

    return 0;
}