#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=200001;
using namespace std;

ll n,g,W[5001],V[5001];
ll dp[2][10001];

int main(){
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out"); 
	cin>>n>>g;
	for(int i=0;i<n;i++){
		cin>>W[i]>>V[i];
	}
	int sw=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=g;j++){
			if(j>=W[i]){
				dp[sw][j]=max(dp[!sw][j],dp[!sw][j-W[i]]+V[i]);
			}
			else dp[sw][j]=dp[!sw][j];
		}
	sw=!sw;
	}
	cout<<dp[!sw][g]<<endl;
}