#include <fstream>
#include <vector>

using namespace std;

int main() {

   ifstream fin("rucsac.in");
  ofstream fout("rucsac.out");

  int n, w;
  int weight, value;

  fin >> n >> w;
  vector<int> profit(w + 1, 0);
  vector<int> actual(w + 1, 0);

  for (int i = 0; i < n; ++i) {
    fin >> weight >> value;
    for (int j = 1; j <= w; ++j) {
      actual[j] = (j - weight >= 0) ?
                  max(profit[j - weight] + value, profit[j]) : profit[j];
    }
    profit = actual;
  }

  fout << profit[w] << "\n";

  fin.close();
  fout.close();
  return 0;
}