#include <bits/stdc++.h>

int main()
{
  std::ifstream in("rucsac.in");

  int n;
  int g;
  in >> n >> g;

  auto dyn = new int *[]
  {
    new int[g + 1] - 1,
    new int[g + 1] - 1,
    new int[g + 1] - 1
  };

  auto price = new int[n + 1];
  auto weight = new int[n + 1];

  for (auto i = 1; i <= n; ++i)
    in >> weight[i] >> price[i];

  for (auto i = 1; i <= n; ++i)
    for (auto j = 1; j <= g; ++j)
    {
      auto l = i % 2;
      auto lf = 1 - l;

      dyn[l][j] = dyn[lf][j];
      if (weight[i] <= j)
        dyn[l][j] = std::max(dyn[lf][j], dyn[lf][j - weight[i]] + price[i]);
    }

  std::ofstream("rucsac.out") << dyn[n % 2][g];
}