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

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

int knapsack(int G, int n){
	
	if(g==0 || n==0) return 0;
	
	if(g[n]>G) return knapsack(G,n-1);
	
	return max(c[n]+knapsack(G-g[n],n-1),knapsack(G,n-1));
}


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];
	}
	cout<<knapsack(Gmax,n);

}