#include <stdio.h>
#include <stdlib.h>

#define MAXN 5000
#define MAXG 10000

int tot[2][MAXG + 1];

int main(){
  FILE *fin, *fout;
  int n, gmax, i, ig, g, p, ul, cu, aux;

  fin = fopen( "rucsac1.in", "r" );
  fscanf( fin, "%d%d", &n, &gmax );
  ul = 0;
  cu = 1;
  for( i = 1; i <= n; i++ ){
    fscanf( fin, "%d%d", &g, &p );
    for( ig = 0; ig < g; ig++ )
      tot[cu][ig] = tot[ul][ig];

    for( ig = g; ig <= gmax; ig++ ){
      tot[cu][ig] = tot[ul][ig] > tot[ul][ig - g] + p ? tot[ul][ig] : tot[ul][ig - g] + p;
    }

    aux = cu;
    cu = ul;
    ul = aux;
  }
  fclose( fin );

  fout = fopen( "rucsac1.out", "w" );
  fprintf( fout, "%d\n", tot[ul][gmax] );
  fclose( fout );

  return 0;
}