#include <bits/stdc++.h>
using namespace std;
#define For(i,a,b); for(int i=a;i<=b;i++)
#define FOR(i,a,b); for(int i=a;i<b;i++)
#define Dow(i,a,b) for (int i=a;i>=b;i--)
#define e '\n'
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fil(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;



inline ll read(){
	ll x=0,f=1;char c=getchar();
	while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
	if (c=='-') f=-1,c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}

int v[5002],w[5002],n,W,a[10004];
 


int main(){
	FAST
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	
	cin >> n >> W;
	For(i,1,n){
		cin >> w[i] >> v[i];
	}
	int rez=0;
	for(int i=1;i<=n;i++){
		for(int j=W-w[i];j>=0;j--){
			if(a[j+w[i]]<a[j]+v[i]){
				a[j+w[i]]=a[j]+v[i];
				rez=max(rez,a[j+w[i]]);
			}
		}
	}

	cout << rez;

return 0;

}