#include <fstream>
using namespace std;

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

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[i+1][j]=((W[i]>j)?(T[i][j]):(max(T[i][j], V[i]+T[i][j-W[i]])));

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

	return 0;
}