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

int n, Gmax, g[5010], c[5010];
int a[10010];
int folosit[5010][10010];
int rs;

int main(){
	
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	
	cin>>n>>Gmax;
	for(int i=1;i<=n;i++){
		cin>>g[i]>>c[i];
	}
	
	for(int i=1;i<=Gmax;i++) a[i]=-1;
	
	for (int i=1;i<=Gmax;i++){
		for (int j=1;j<=n;j++){
			if(g[j]<=i && a[i-g[j]]!=-1 && !folosit[j][i-g[j]])
				if(c[j]+a[i-g[j]]>a[i]){
					a[i]=c[j]+a[i-g[j]];
					for(int k=1;k<=n;k++) folosit[k][i]=folosit[k][i-g[j]];
					folosit[j][i]=1;
				} 
		}
	}
	
	rs=Gmax;
	while(a[rs]!=-1) rs--;
	cout<<a[rs];
}