//ALEXANDRU MICLEA

#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

#include <fstream>
ifstream cin("rucsac.in"); ofstream cout("rucsac.out");

int w[10005], p[5005];
int d[5005][10005];

int main() {

	int N, G;
	cin >> N >> G;

	int l = 0;
	for (int i = 1; i <= N; i++, l = 1 - l) {
		cin >> w[i] >> p[i];
		for (int j = 0; j <= G; j++) {
			d[1 - l][j] = d[l][j];

			if (w[i] <= j) {
				d[1-l][j] = max(d[1-l][j], d[i - 1][j - w[i]] + p[i]);
			}
		}
	}

	cout << d[l][G];

	return 0;
}