#include <bits/stdc++.h>

using namespace std;

int n,g,G[5010],P[5010];
long long DP[10010],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++){
		for(int j=g;j>=G[i];j--){
			DP[j]=max(DP[j-G[i]]+P[i],DP[j]);
			sol=max(DP[j],sol);
		}
	}
	fout<<sol;
}