#include <cstdio>
#include <iostream>

#define MAX_G 10010
#define INF 20000000

using namespace std;

int d[2][MAX_G], n, g;

int main() {
  int w, c;

  freopen("rucsac.in", "r", stdin);
  freopen("rucsac.out", "w", stdout);

  scanf ("%d %d", &n, &g);

  for(int j = 0; j <=g; j ++)
    d[0][j] = -INF;

  for(int i = 1; i <= n; i ++) {
    scanf("%d %d", &w, &c);
    for(int j = 0; j <= g; j ++) {
        if (j - w == 0)
          d[i % 2][w] = max (d[(i - 1) % 2][w], c);
	else
	  if (j - w > 0)
	    d[i % 2][j] = max (d[(i - 1) % 2][j], d[(i -1) % 2][j - w] + c);
	  else
	    d[i % 2][j] = d[(i - 1) % 2][j];
    }
  }

  printf ("%d\n", d[n % 2][g]);
  return 0;
}