#include <cstdio>

using namespace std;

const int NMAX = 5005;
const int GMAX = 10005;
int N, G;
int bag[NMAX][2];
int matrix[NMAX][GMAX];

void read() {
  freopen("rucsac.in", "r",stdin);
  freopen("rucsac.out", "w",stdout);
  scanf("%i%i", &N, &G);
  for(int i = 1; i <= N; i++)
    scanf("%i%i", &bag[i][0], &bag[i][1]);
}

void solve() {
  for(int i = 1; i <= N; i++)
    for(int j = 1; j <= G; j++) {
      matrix[i][j] = matrix[i-1][j];
      if(j - bag[i][0] >= 0 && matrix[i-1][j-bag[i][0]] + bag[i][1] > matrix[i][j])
        matrix[i][j] = matrix[i-1][j-bag[i][0]] + bag[i][1];
    }
}

int main() {
  read();
  solve();
  printf("%i", matrix[N][G]);
	return 0;
}