#include <bits/stdc++.h>
#define forn(i,n) for(int i = 0;i<n;i++)
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define f first
#define s second
#define all(a) a.begin(),a.end()
#define cty cout<<"YES\n"
#define ctn cout<<"NO\n"
using namespace std;

#define MAX 500

vector<pair<int,int>>a(1000);

int dp[1000][10001];


int rucsac(int n, int w){

    if(n == -1 || w == 0) return 0;

    else if ( w < a[n].f) return rucsac(n-1,w);

    else if(dp[n][w] != -1) return dp[n][w];


    int v1 = rucsac(n-1,w-a[n].f) + a[n].s;
    int v2 = rucsac(n-1,w);

    dp[n][w] = max(v1,v2);

    return dp[n][w];









}
 

void solve(){

     memset(dp,-1,sizeof(dp));

     int n,w;
     cin >> n >> w;

     forn(i,n){
        cin >> a[i].f >> a[i].s;
     }

    cout << rucsac(n-1,w);


}

int main()
{   

    ios::sync_with_stdio(false); cin.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("in.txt","r",stdin);
     freopen("out.txt","w",stdout);
    #endif  

    int t = 1;;
  //  cin >> t;
    while(t--) solve();

  




   
    return 0;
}