#include <bits/stdc++.h>

int dyn[3][10'001];
int price[5'001];
int weight[5'001];

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

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

  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];
}