#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[5002][5002];
 


int main(){
	FAST
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	
	cin >> n >> W;
	For(i,1,n){
		cin >> w[i] >> v[i];
	}

	for(int i=1;i<=n;i++){
		for(int j=0;j<=W;j++){
			if(w[i]>j){
				a[i][j]=a[i-1][j];
			}
			else {
				a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+v[i]);
			}
		}
	}

	cout << a[n][W];

return 0;

}