// Original C++ solution (slower):
#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_N = 111, MAX_W = 111111;

int w[MAX_N], v[MAX_N];

int dp[MAX_N][MAX_W];



int main() {

   int N, W;

   cin >> N >> W;

   rep (i, N) {

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

   }



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

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

         if (j >= w[i]) {

            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);

         } else {

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

         }

      }

   }



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



   return 0;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem: