#include <fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int maxn=5005, maxg=10005;

int L1[maxg],L2[maxg],W[maxn],P[maxn];
int i,cw,N,G;

int main() {
	fin >> N >> G;
	for(i=1;i<=N;i++) fin >> W[i] >> P[i];
	for(i=1;i<=N;i++) {
		for(cw=0;cw<=G;cw++) {
			if(cw-W[i]<0) L2[cw]=L1[cw];
			else L2[cw]=max(L1[cw],L1[cw-W[i]]+P[i]);
		}
		memcpy(L1,L2,sizeof(L1));
	}
	fout << L2[G];
}