#include <bits/stdc++.h>

using namespace std;

int n,g,G[5010],P[5010],DP[2][5010];

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];
	}
	DP[0][G[0]]=P[0];
	for(int i=1;i<n;i++){
		for(int j=0;j<=g;j++){
			if(DP[(i-1)%2][j-G[i]])DP[i%2][j]=max(DP[(i-1)%2][j-G[i]]+P[i],DP[i%2][j]);
			DP[i%2][j]=max(DP[(i-1)%2][j],DP[i%2][j]);
		}
	}
	fout<<DP[(n-1)%2][g];
}