#include <stdio.h>

long v[10001];
int w[5001], p[5001];

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

  fin = fopen ( "rucsac.in", "r" );
  fout = fopen ( "rucsac.out", "w" );
  fscanf ( fin, "%d%d", &n, &g );
  for ( i = 1; i <= n; i++ )
    fscanf ( fin, "%d%d", &w[i], &p[i] );
  for ( i = 1; i <= n; i++ )
   for ( j = g; j >= w[i]; j-- ) {
     if ( v[j] > v[j-w[i]] + p[i] )
       v[j] = v[j];
     else
       v[j] = v[j-w[i]] + p[i];
   }
  fprintf ( fout, "%d", v[g] );
  return 0;
}