#include <bits/stdc++.h>
using namespace std;
long long n,m;
long long w[30005],v[30005];
long long dp[15000][16000];//16190
int main(){
	freopen("delicious.in","r",stdin);
	freopen("delicious.out","w",stdout);
	scanf("%lld %lld",&n,&m);
	for(long long i=1;i<=n;++i){
		scanf("%lld %lld",&w[i],&v[i]);
	}
	for(register long long i=1;i<=n;++i){
		for(register long long j=0;j<=m;++j){
			dp[i][j]=dp[i-1][j];
			if(j >= w[i]){
				dp[i][j] = max(dp[i-1][j],(dp[i-1][j-w[i]] + v[i]));
			}
		}
	}
	printf("%lld",dp[n][m]);
	return 0;
}
//#include <bits/stdc++.h>
//using namespace std;
//long long n,m;
//long long ans;
//struct apple{
//	long long a,b,c;
//}a[30005];
//inline bool cmp(apple x,apple y){
//	if(x.c == x.c){
//		return x.a<y.a;
//	}
//	else{
//		return x.c>y.c;
//	}
//}
//int main(){
//	scanf("%lld %lld",&n,&m);
//	for(int i=1;i<=n;++i){
//		scanf("%lld %lld",&a[i].a,&a[i].b);
//		a[i].c = a[i].b/a[i].a;
//	}
//	sort(a+1,a+n+1,cmp);
//	for(int i=1;i<=n;++i){
//		if(m>=a[i].a){
//			m -= a[i].a;
//			ans += a[i].b;
//		}
//		else{
//			break;
//		}
//	}
//	printf("%lld",ans);
//	return 0;
//}