#include <fstream>
using namespace std;
 
int weight[5001], price[5001];
int Optim[10001];
 
int main() {
    ios::sync_with_stdio(0);
    int n, G, sol = 0, i, j;   

	ifstream f("rucsac.in");
	f >> n >> G;
	for (i = 1; i <= n; i++) 
		f >> weight[i] >> price[i];
    f.close();

	Optim[0] = 0;

    for (i = 1; i <= n; i++)
		for (j = G - weight[i]; j >= 0; j--) {
            if (Optim[j + weight[i]] < Optim[j] + price[i]) {
				Optim[j + weight[i]] = Optim[j] + price[i];
				if (Optim[j + weight[i]] > sol)
					sol = Optim[j + weight[i]];
			}
		}

    ofstream g("rucsac.out");
	g << sol;
    g.close();

	return 0;
}