#include<bits/stdc++.h>

using namespace std;

int n,g,a,b,c[5100][10100];

pair <int,int> r[5100];

int main(){
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	cin>>n>>g;
	for(int i=1;i<=n;i++){
		cin>>a>>b;
		r[i]=make_pair(a,b);
	}
	
	//sort(r+1,r+n+1);
	//for(int i=1;i<=g;i++)
	//	c[1][i]=r[1].second;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=g;j++){
			c[i][j]=c[i-1][j];
			if(r[i].first<=j) 
			 c[i][j]=max(c[i-1][j],c[i-1][j-r[i].first]+r[i].second);	
		}
	cout<<c[n][g];
	return 0;
}