#include<bits/stdc++.h>

using namespace std;

int n,g,a,b,c[5100][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];
	}
	

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