// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define ll long long

#define vvi vector<vector<int>>

#define vec vector

#define pq priority_queue

#define all(v) (v).begin(), (v).end()

#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))

#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))

#define debug(x) cerr << #x << ": " << x << endl;

#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;

#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;

#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;

#define line() cerr << "---------------" << endl;



const int dx[] = {1, -1, 0, 0};

const int dy[] = {0, 0, -1, 1};



template<typename T>

void printA(vector<T> &printArray, char between = ' ') {

   int paSize = printArray.size();

   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}

   if (between != '\n') {cerr << endl;}

}



// ------------------------------------------------------------------------------------------



const int NN = 111;

const int WW = 11111;

int N, W;

int w[NN], v[NN];



int bitBruteForth() {

   int ans = 0;

   rep (mask, (1<<N)) {

      int value = 0, weight = 0;;

      rep (i, N) {

         if ((mask>>i)&1) {

            value += v[i];

            weight += w[i];

         }

      }

      if (weight <= W) {

         ans = max(ans, value);

      }

   }

   return ans;

}



// int dfs(今の状態) {

//    int ret = 0;

//    for (...) ret += dfs(次の状態);

//    return ret;

// }



int dp[NN+1][WW+1];



int rec(int idx, int wLim) {

   if (idx == N) {

      return 0;

   } else if (wLim < w[idx]) {

      return rec(idx + 1, wLim);

   } else {

      int in = rec(idx + 1, wLim - w[idx]) + v[idx];

      int noIn = rec(idx + 1, wLim);

      return max(in, noIn);

   }

}



int memo(int idx, int wLim) {

   if (dp[idx][wLim] >= 0) {

      return dp[idx][wLim];

   }



   int res;

   if (idx == N) {

      res = 0;

   } else if (wLim < w[idx]) {

      res = memo(idx + 1, wLim);

   } else {

      int in = memo(idx + 1, wLim - w[idx]) + v[idx];

      int noIn = memo(idx + 1, wLim);

      res = max(in, noIn);

   }



   return dp[idx][wLim] = res;

}



int main() {

   cin >> N >> W;

   rep (i, NN+1) {

      rep (j, WW+1) {

         dp[i][j] = -1;

      }

   }

   rep (i, N) {

      cin >> v[i] >> w[i];

   }



   // cout << rec(0, W) << endl;

   cout << memo(0, W) << endl;



   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.132636126764121x):
#include <bits/stdc++.h>

using namespace std;



#define ll long long

#define vvi vector<vector<int>>

#define vec vector

#define pq priority_queue

#define all(v) (v).begin(), (v).end()

#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());

#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))

#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))

#define debug(x) cerr << #x << ": " << x << endl;

#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;

#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;

#define debugB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;

#define line() cerr << "---------------" << endl;



const int dx[] = {1, -1, 0, 0};

const int dy[] = {0, 0, -1, 1};

const double PI = 3.14159265358979323846;



template<typename T>

void printA(vector<T> &printArray, char between = ' ') {

   int paSize = printArray.size();

   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}

   if (between != '\n') {cerr << endl;}

}



// ------------------------------------------------------------------------------------------



const int MAX_NUM = 111, MAX_WEIGHT = 11111;

int N, W;

int weight[MAX_NUM], value[MAX_NUM];

int dp[MAX_NUM][MAX_WEIGHT];



int main() {

   cin >> N >> W;

   rep (i, N) {

      cin >> value[i] >> weight[i];

   }



   for (int i = 0; i < N; i++) {

      for (int j = 0; j <= W; j++) {

         if (j >= weight[i]) {

            dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i]);

         } else {

            dp[i+1][j] = dp[i][j];

         }

      }

   }



   cout << dp[N][W] << endl;



   return 0;

}