#include<bits/stdc++.h>
#define maxn 5001
#define maxg 10001

using namespace std;

int w[maxn], p[maxn];
int v[maxg];

int main() {

	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	int n, G;
	fin>>n>>G;

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

	v[0] = 0;
	int nr = 0;

	for( int i = 1; i <= n; ++i)
		for( int j = G - w[i]; j >= 0; --j) {
			if( v[j+w[i]] < v[j] + p[i] )
			{
				v[j+w[i]] = v[j] + p[i];
				if( v[j+w[i]] > nr)
					nr = v[j+w[i]];
			}
		}
	fout<<nr;
	return 0;
}