#include <fstream>
using namespace std;

int N, G, W[5000], V[5000], T[2][10001];

void change(){
	int i;

	for (i=0; i<=G; i++)
		T[0][i]=T[1][i];
}

int main(){
	int i, j;

	//ifstream fin ("knapsack.in");
	ifstream fin ("rucsac.in"); //infoarena
	fin >> N >> G;
	for (i=0; i<N; i++)
		fin >> W[i] >> V[i];
	fin.close();

	for (i=0; i<=N; i++)
		T[i][0]=0;
	for (i=0; i<=G; i++)
		T[0][i]=0;

	for (i=0; i<N; i++){
		for (j=0; j<=G; j++)
			T[1][j]=((W[i]>j)?(T[0][j]):(max(T[0][j], V[i]+T[0][j-W[i]])));
		change();
	}

	//ofstream fout ("knapsack.out");
	ofstream fout ("rucsac.out"); //infoarena
	fout << T[1][G] << '\n';
	fout.close();

	return 0;
}