#include<bits/stdc++.h>

using namespace std;

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

int w[5010],p[5010];

int main(){
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	cin>>n>>g;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>p[i];
	}
	int l=0;

	for(int i=1;i<=n;++i,l=1-l)
		for(int j=0;j<=g;j++){
			c[1-l][j]=c[l][j];
			if(w[i]<=j) 
			 c[1-l][j]=max(c[1-l][j],c[l][j-w[i]]+p[i]);	
		}
	cout<<c[l][g];
	return 0;
}