#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

#define GMax 10001

using namespace std;

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

int n, g;
vector<int> w, p;
int ruc[GMax];
bitset<5001> ex[GMax];

void read() {
	in>>n>>g;
	for (int i=1;i<=n;i++) {
		int weight, profit;
		in>>weight>>profit;

		w.push_back(weight);
		p.push_back(profit);
	}
}

void solve() {
	for (int i=0;i<=g;i++) {
		for (int j=0;j<n;j++) {
			if (i - w[j] >= 0) {
				if (ex[i-w[j]][j] == 0) {
					if (ruc[i-w[j]] + p[j] > ruc[i]) {
						for (int k=0;k<n;k++)
							ex[i][k] = ex[i-w[j]][k];
						ex[i][j] = 1;

						ruc[i] = ruc[i-w[j]] + p[j];
					}
				}
			}
		}
	}

	out<<ruc[g]<<endl;
}

int main() {

	read();
	solve();

	in.close();
	out.close();

	return 0;
}