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

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