#include <bits/stdc++.h>
using namespace std;
struct Item {
  int value, weight;
};
Item items[105];
int C[105][10005], G[105][10005];
int N, W;
int compute() {
  for (int i = 0; i <= W; ++i) {
    C[0][i] = 0;
  }
  for (int i = 0; i <= N; ++i) {
    C[i][0] = 0;
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= W; ++j) {
      C[i][j] = C[i - 1][j];
      if (j < items[i].weight) continue;
      if (C[i - 1][j - items[i].weight] + items[i].value > C[i - 1][j]) {
        C[i][j] = C[i - 1][j - items[i].weight] + items[i].value;
      }
    }
  }
  return C[N][W];
}
void input() {
  cin >> N >> W;
  for (int i = 0; i < N; ++i) {
    cin >> items[i + 1].value >> items[i + 1].weight;
  }
}
int main() {
  input();
  cout << compute() << endl;
}
