#include <bits/stdc++.h>
using namespace std;

int main(){
	ifstream cin("rucsac.in"); ofstream cout("rucsac.out");
	long long n, g;
	cin>>n>>g; long long w[n], p[n], a[n+1][g+1];
	
	a[n][0]=0;
	for(int i=0; i<n; i++){
		cin>>w[i]>>p[i];
		a[i][0]=0;
	}
	for(int i=0; i<g+1; i++){
		a[0][i]=0;
	}
	
	a[0][0]=0;
	for(int i=1; i<n+1; i++){
		for(int j=1; j<g+1; j++){
			
			if (j-w[i-1]<0){a[i][j]=a[i-1][j];} else{
				a[i][j]=max( a[i-1][j], p[i-1]+a[i-1][ max(a[0][0], j-w[i-1]) ] );
			}
		} 
	}	
	cout<<a[n][g];	
	
	return 0;
}