#include <iostream>
#include <fstream>
#define D 1
using namespace std;
const int NMAX = 5000;             // nr maxim de obiecte
const int GMAX = 10000;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int a[GMAX+1];
int n, G, g;                       // nr obiectelor, capacitatea rucsacului
int vol[NMAX+1], val[NMAX+1];
int main() {
  fin >> n >> G;
  for( int i = 1; i <= n; i++ )
    fin >> vol[i] >> val[i];

  for( int i = 1; i <= n; i++ ) {
    for( int j = G; j >= vol[i]; j-- ) {
      a[j] = max ( a[j], a[j-vol[i]] + val[i] );
    }
   if ( D ) {
     for( int j = 1; j <= G; j++ )
        cout << a[j] << " ";
     cout << '\n';
   }
  }
  fout << a[G] << '\n';           //   val maxima obtinua
  return 0;
}