#include <bits/stdc++.h>

using namespace std;

int n,g,G[5010],P[5010];
long long DP[2][5010],sol=0;

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

int main(){
	fin>>n>>g;
	for(int i=0;i<n;i++){
		fin>>G[i]>>P[i];
	}
	memset(DP,0,sizeof DP);
	for(int i=0;i<n;i++){
		memset(DP[i%2],0,sizeof DP[i%2]);
		for(int j=0;j<=g;j++){
			DP[i%2][j]=DP[(i+1)%2][j];
			if(j-G[i]>=0)DP[i%2][j]=max(DP[(i+1)%2][j-G[i]]+P[i],DP[i%2][j]);
			sol=max(DP[i%2][j],sol);
		//	if(j)DP[i%2][j]=max(DP[i%2][j-1],DP[i%2][j]);
		//	cout<<DP[i%2][j]<<' ';
		}
		//cout<<'\n';
	}
	fout<<sol;
}