#include <fstream>
using namespace std;

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

int n, q, wtmx, val, wt, i, j, t[5][10005];

int mx(int a, int b){
  if (a > b)
    return a;
  return b;
}

int main()
{
  fin >> n >> wtmx;
  for (i = 1; i <= n; i ++){
    fin >> wt >> val;
    if (i == 1)
      q = 1;
    else
      q = 2;
    for (j = 1; j <= wtmx; j ++)
       if (wt > j)
         t[q][j] = t[q - 1][j];
       else
         t[q][j] = mx(t[q - 1][j], t[q - 1][j - wt] + val);
    if (i > 1)
      for (j = 1; j <= wtmx; j ++){
        t[1][j] = t[2][j];
        t[2][j] = 0;
      }
  }
  fout << t[1][wtmx];
  return 0;
}