#include <fstream>
#define NMAX 5001
#define VALMAX 10001
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int w[VALMAX], p[VALMAX], dp[NMAX][VALMAX];
int main() {
  int n, g, i, j;
  fin >> n >> g;
  for ( i = 0; i < n; i++ )
    fin >> w[i] >> p[i];
  for ( i = 0; i < n; i++ ) {
    for ( j = 0; j <= g; j++ ) {
      if ( w[i] <= j )
        dp[i][j] = max(dp[i - 1][j - w[i]] + p[i], dp[i - 1][j]);
      else
        dp[i][j] = dp[i - 1][j];
    }
  }
  fout << dp[n - 1][g];
  return 0;
}