#include <stdio.h>
#define min( a, b ) a < b ? b : a

int cost[1001], e[1001]; 
int minCost[1001][5002];

int main() {
  FILE *fin = fopen( "energii.in", "r" );
  FILE *fout = fopen( "energii.out", "w" );
  int G, W, i, j;
  
  fscanf( fin, "%d%d", &G, &W );
  for ( i = 1; i <= G; ++i ) {
	fscanf( fin, "%d%d", &cost[i], &e[i] );
  }
  for ( i = 1; i <= G; ++i ) {
	for ( j = 0; j <= W; ++j ) {
	  if ( e[i] <= j ) {
	    minCost[i][j] = min( minCost[i - 1][j], minCost[i - 1][j - e[j]] + cost[i] );
	  } else {
        minCost[i][j] = min( minCost[i - 1][j], cost[i] );
	  }
	}
  }
  fprintf( fout, "%d", minCost[G][W] );
  fclose( fin );
  fclose( fout );
  return 0;
}