#include <iostream>
#include <stdio.h>
#define NMAX 5000
#define GMAX 10000

using namespace std;

int maxim(int a, int b) {
  return a < b ? b : a;
}

struct produs {
  int greutate, pret;
};

int dp[GMAX + 1];
produs v[NMAX + 1];

int main() {
  FILE *fin, *fout;
  int n, g, i, sol, j;

  fin = fopen("rucsac.in", "r");
  fscanf(fin, "%d%d", &n, &g);

  sol = 0;
  for (i = 0; i < n; i++) {
    fscanf(fin, "%d%d", &v[i].greutate, &v[i].pret);
    for (j = g; j >= v[i].greutate; j--) {
      dp[j] = maxim(dp[j], dp[j - v[i].greutate] + v[i].pret);
      sol = maxim(sol, dp[j]);
    }
  }

  fout = fopen("rucsac.out", "w");
  fprintf(fout, "%d", sol);
  fclose( fout );
  return 0;
}