#include <fstream>
#define nmax 5001
#define gmax 10001

using namespace std;


ifstream f("rucsac.in");
ofstream g("rucsac.out");
int mat[nmax][gmax], w[nmax]={0}, p[nmax];
int main(){
	
	int n, G, i, j, weight, dp[gmax]={0};
	f>>n>>G;
	for(i=1;i<=n;i++)
	  f>>w[i]>>p[i];
//met 1
/*	for(i=1;i<=n;i++)
		for(weight=0;weight<=G;weight++){
			mat[i][weight]=mat[i-1][weight];
			if(w[i]<=weight){
				mat[i][weight]=max(mat[i][weight],mat[i-1][weight-w[i]]+p[i]);
			}
		}
	g<<mat[n][G];
*/
//met 2
	for(i=1;i<=n;i++)
		for(j=G;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+p[i]);
		}
 g<<dp[G]<<"\n";
}