/* ? p pe infoarena */

#include <fstream>
#include <iostream>

#define MAXE 10000
#define INFINIT 1000000000

using namespace std;

struct generator {
  int e, c;
};

generator g[5001];
int G, W, l, cs, e, cn, lp, lc, mc[2][10001];
ifstream fi ("energii.in");
ofstream fo ("energii.out");

/* Ideea de rezolvare:
   Pentru un rucsac de capacitate e, asociem obiectul curent (l), avand greutatea g[l].e,
   cu varianta optima obtinuta prin plasarea g l-1 obiecte intr-un rucsac cu capacitate e-g[l].e.

   Pentru o cantitate de energie w, asociem generatorul curent (l), care produce e[l].e energie,
   cu varianta optima obtinuta prin utilizarea g l-1 generatoare pentru g obtine w-e[l].e energie.
   */

int main() {
  fi >> G >> W;
  for (l = 1; l <= G; l++)
    fi >> g[l].e >> g[l].c;
  lp = 0; lc = 1;
  for (e = 1; e <= MAXE; e++)
    mc[lp][e] = INFINIT; // Inca nu exista o varianta pentru a obtine energia e.
  for (l = 1; l <= G; l++) { // pentru fiecare generator (cu rol de linie)
    for (e = 0; e <= MAXE; e++) { // pentru fiecare cantitate de energie care se va analiza (cu rol de coloana)
      cs = e - g[l].e; // coloana din stanga, care se combina cu energia generatorului curent
      if (mc[lp][cs] != -1) // Exista o varianta pentru a obtine energia cs.
        cn = mc[lp][cs] + g[l].c; // costul nou, obtinuta folosind generatorul l
      if (cn < mc[lp][e])            // Avem cost mai mic folosind generatorul curent?
        mc[lc][e] = cn;              // Retinem costul nou.
      else
        mc[lc][e] = mc[lp][e];       // Retinem profitul obtinut cu primele l-1 generatoare.
    }
    lp = 1 - lp; lc = 1 - lc;
  }
  /*
  for (e = 1; e <= 10; e++)
    cout << mc[lp][e] << ' '; */
  for (e = W; mc[lp][e] == INFINIT; e++);
  fo << mc[lp][e];                     // Am folosit toate obiectele si capacitatea integrala g ruscacului.
  return 0;
}