#include<iostream>
#include<algorithm>
#include<utility>
using namespace std;
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775807
#define LL_MAX 9223372036854775807

int N,W;
pair<int,int> b[100];
long long dp[100][100100];

long long solve(int now, int wlim){
	if(wlim < 0) return LL_MIN;
	if(now == N) return 0;
	if(dp[now][wlim] != -1) return dp[now][wlim];
	return dp[now][wlim] = max( solve(now+1, wlim) , solve(now+1, wlim-b[now].first) + b[now].second );
}

int main(){
	cin >> N >> W;
	for(int i=0; i<N; i++){
		for(int j=0; j<=W; j++){
			dp[i][j]=-1;
		}
	}
	for(int i=0; i<N; i++){
		int we,va;
		cin >> we >> va;
		b[i]=make_pair(we,va);
	}
	
	cout << solve(0,W) << endl;
	return 0;
}


/*
#include<iostream>

using namespace std;
int n;
int happy[100100][5];
int dp[100100][5];

int solve(int now, int act){
	if(dp[now][act] != -1) return dp[now][act];
	if(now==n)return 0;
	else{
		int tmp = -1;
		for(int i=0; i<3; i++){
			if(i!=act){
				tmp=max(tmp,solve(now+1,i)+happy[now][i]);
			}
		}
		return dp[now][act]=tmp;
	}
}

int main(){
	cin >> n;
	dp[n][0] = dp[n][1] = dp[n][2] = -1;
	for(int i=0; i<n; i++){
		cin >> happy[i][0] >> happy[i][1] >> happy[i][2];
		dp[i][0] = dp[i][1] = dp[i][2] = -1;
	}
	cout << solve(0,5) << endl;

	return 0;
}

*/

/*
#include<iostream>

using namespace std;
int n,k;
int height[100100];
int dp[100100];

int solve(int now){
	if(dp[now]!=-1)return dp[now];
	if(now==n-1)return 0;
	int tmp=999999999;
	for(int i=now+1; i<n; i++){
		if(i-now>k)break;
		else{
			tmp=min(tmp,solve(i)+abs(height[now]-height[i]));
		}
	}
	return dp[now]=tmp;
}

int main(){
	cin >> n >> k;
	for(int i=0; i<n; i++){
		cin >> height[i];
		dp[i] = -1;
	}

	cout << solve(0) << endl;

	return 0;
}



*/


//チーズ
/*
//まずはN=1の場合で考える

#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
int h,w,n;//n=1
char town[1010][1010];
int start[2],goal[2];//i,j
int time[1010][1010];

//sarch
int solve(int H,int W){
	if(time[H][W] != 9999999)return time[H][W];
	//if


}


int main(){
	//imput
	cin >> h >> w >> n;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			cin >> town[i][j];
			//memorise start and goal
			if(town[i][j]=='S'){
				start[0]=i;
				start[1]=j;
			}
			if(town[i][j]=='1'){
				goal[0]=i;
				goal[1]=j;
			}
			//十分大きな数で初期化
			time[i][j]=9999999;
		}
	}
	//imput end



	return 0;
}
*/


/*
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

int main(){


	return 0;
}

*/

//union find & prime
/*
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>

using namespace std;
int n;
int num[100100];
vector<pair<int,int>>sortednum;
int par[100010];
map<int,int>ppid;

int neid(int x){
	if(par[x]==x)return x;
	else{
		return par[x]=neid(par[x]);
	}
}

void primenum(int inow, int NUM){
	for(int i=2; i*i<=NUM; i++){
		if(NUM%i==0){
			if(ppid.count(i)==0){
				ppid[i]=inow;
			}
			else{
				par[neid(ppid[i])]=inow;
			}
			while(NUM%i==0)NUM/=i;
		}
	}
	if(NUM!=1){
		if(ppid.count(NUM)==0){
			ppid[NUM]=inow;
		}
		else{
			par[neid(ppid[NUM])]=inow;
		}

	}
}

int main(){
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> num[i];
		sortednum.push_back(make_pair(num[i],i));
		par[i]=i;
		primenum(i,num[i]);
	}

	sort(sortednum.begin(),sortednum.end());
	int ans=1;

	for(int i=0; i<n; i++){
		if(neid(i)!=neid(sortednum[i].second)){
			ans=0;
			break;
		}
	}
	cout << ans << endl;

	return 0;
}
*/

//djikstra
/*
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
int INF = 10000000;
priority_queue< pair<int,int> > que; //INF-cost,i
int cost[1000];
for(int i=0; i<1000; i++) cost[i] = INF;
cost[0] = 0;
que.push(make_pair(INF-0, 0));
while(!que.empty){
	int now = que.top().second;
	for(int i=0; i<tonari[now].size(); i++){
		if(cost[tonari[now][i]] > cost[now] + distance[now][tonari[now][i]){
			cost[tonari[now][i]] = cost[now] + distance[now][tonari[now][i];
			que.push(make_pair(INF-cost[tonari[now][i]], tonari[now][i]));
		}
	}
	que.pop();
}
*/

Measured memory_bytes: 78464