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

  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);
    crt = i % 2;
    ant = (i - 1) % 2;
    for(int j = 0; j <= g; j ++) {
	d[crt][j] = d[ant][j];
	if (j - w >= 0)
	    d[crt][j] = (d[crt][j] > d[ant][j - w] + c) ? d[crt][j]:
	      d[ant][j - w] + c;
    }
  }

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