#include <fstream>
#include <vector>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n, wm, v1[10002], v2[10002];
vector<pair<int, int>> vp;
int main() {
	cin >> n >> wm;
	vp.push_back({ -1, -1 });
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		vp.push_back({ y, x });
	}
	int act = 1, maxi = 0;
	for (int i = 1; i <= n; i++) {
		if (act == 1) {
			for (int j = 0; j <= wm; j++) {
				if (j - vp[i].second >= 0 && v1[j]< v1[j - vp[i].second] + vp[i].first) {
					v2[j] = v1[j - vp[i].second] + vp[i].first;
					if (maxi < v2[j]) {
						maxi = v2[j];
					}
				}
				else {
					v2[j] = v1[j];
				}
			}
			act = 0;
		}
		else {
			for (int j = 1; j <= wm; j++) {
				if (j - vp[i].second >= 0) {
					v1[j] = v2[j - vp[i].second] + vp[i].first;
					if (maxi < v1[j]) {
						maxi = v1[j];
					}
				}
				else {
					v1[j] = v2[j];
				}
			}
			act = 1;
		}
	}
	cout << maxi;
}