#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int MAXN = 5000;
const int MAXG = 10000;

int d[MAXN + 1][MAXG + 1];
int val[MAXN + 1], greutate[MAXN + 1];

int main(){

  int n, g, i, j;
  in>>n>>g;

  for( i = 1; i <= n; i++ )
    in>>greutate[i]>>val[i];

  d[0][0] = 0;
  for( i = 1; i <= n; i++ ){
    for( j = 0; j <=g; j++ ){
      d[i][j] = d[i - 1][j];
      if( greutate[i] <= j )
        d[i][j] = max( d[i][j], d[i - 1][j - greutate[i]] + val[i]);
    }
  }

  out<<d[n][g];
  return 0;
}