#include<bits/stdc++.h>
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) max(a,min(b,c))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/__gcd(a,b)
#define print1(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" "
#define print21(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<a[i][j]<<" ";}cout<<endl;}
#define scan1(a,n) for(int i=1;i<=n;i++) cin>>a[i]
#define scan(a,n) for(int i=0;i<n;i++) cin>>a[i]
#define print(a,n) for(int i=0;i<n;i++) cout<<a[i]<<" "
#define int long long
#define double float
#define float long double
#define vi vector<int>
#define si set<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define mkp make_pair
#define mod 1000000007
#define ff first
#define ss second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mset(m,v) memset(m,v,sizeof(m))
#define bs binary_search
#define cout1(a) cout<<a<<endl
#define cout2(a,b) cout<<a<<" "<<b<<endl
#define cout3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define cout4(a,b,c,d) cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl
#define endl '\n'
using namespace std;
bool comp(int x,int y){
	if(x>=y)
	return true;
	return false;
} 
bool compare(const pii &i,const pii &j){
	return i.ss<j.ss;
}
bool compare1(const pii &i,const pii &j){
	return i.ff>j.ff;
}
string decitobinary(int n){
	string s="";
	while(n>0){
		s=to_string(n%2)+s;
		n=n/2;
	}
	return s;
}
int binarytodeci(string s){
	int n=0;
	reverse(s.begin(),s.end());
	for(int i=0;i<s.length();i++){
		string t="";
		t+=s[i];
		n+=(int)pow(2,i)*stoi(t);
	}
	return n;
}
double intlog(double base,double x){
    return (log(x)/log(base));
}
int fact(int n){
    int res=1; 
    for(int i=2;i<=n;i++) 
    res=res*i; 
    return res; 
}
int ncr(int n, int k)  
{  
    int res = 1;  
    if(k>n-k)  
    k=n-k;  
    for(int i=0;i<k;++i){
        res*=(n-i);  
        res/=(i+1);  
    }  
    return res;  
}
bool ispalindrome(string str,int l,int h){
    while(h>l){
        if (str[l++]!=str[h--]) 
        return 0;
    } 
    return 1;
} 
  const int N=1e6+3;
  vector<int> adj[N];
  bool vis[N];
  
	void dfs(int u){
	vis[u]=true;
		for(int v:adj[u]){
			if(vis[v]){
				cout<<u<<" ";
				break;
			}
			dfs(v);
		}
	}
int compute_hash(string s){
	int p=31,hash=0,po=1;
	for(char c:s){
		hash+=(c-'a'+1)*po%mod;
		po=(po*p)%mod;
	}
	return hash;
}
vector<vector<int>> group_identical_strings(vector<string> const& s) {
    int n = s.size();
    vector<pair<long long, int>> hashes(n);
    for (int i = 0; i < n; i++)
        hashes[i] = {compute_hash(s[i]), i};
    sort(hashes.begin(), hashes.end());
    vector<vector<int>> groups;
    for (int i = 0; i < n; i++) {
        if (i == 0 || hashes[i].first != hashes[i-1].first)
        groups.emplace_back();
        groups.back().push_back(hashes[i].second);
    }
    return groups;
}
bool isarraysort(int a[],int i,int j){
    if(j==i)
    return 1;
    if(a[j]<a[j-1])
    return 0;
    return isarraysort(a,i,j-1);
}
void solve(){
    int n,m;
    cin>>n>>m;
    int w[n+1],v[n+1];
    for(int i=1;i<=n;i++)
    cin>>w[i]>>v[i];
    int dp[n+1][m+1];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i==0||j==0)
            dp[i][j]=0;
            else if(w[i]>j)
            dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]);
        }
    }
    cout<<dp[n][m];

}
int32_t main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int t=1;
	// cin>>t;
	while(t--){
		solve();
   }
}





Measured memory_bytes: 102656