#include <fstream>
#include <string.h>
using namespace std;

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

int L1[10005],L2[10005],W[5005],P[5005];
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(W[i] > cw) L2[cw]=L1[cw];
			else L2[cw]=max(L1[cw],L1[cw-W[i]]+P[i]);
		}
		memcpy(L1,L2,sizeof(L1));
	}
	fout << L2[G];
}