#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, ant = 1, crt = 0;

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

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

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

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