#include <fstream>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;
typedef struct per{
  int g,v;
}per;
ifstream in("energii.in");
ofstream out("energii.out");
int max(int a,int b)
{
  return a > b ? a : b;
}
int N,G;
per vec[6005];
int sol[10005];
int last = 10000;
void DP()
{
  for(int i = 1; i <= N;i++)
  {
    for(int j = G - vec[i].g; j >= 0; j--)
    {
      if(sol[j] + vec[i].v < sol[j+vec[i].g])
      {
        sol[j+vec[i].g] = sol[j] + vec[i].v;
        if(last > sol[j+vec[i].g])
          last = sol[j+vec[i].g];
      }
    }
  }
  out<<last;
}

int main()
{
  in >> N >> G;
  for(int i = 1; i <= N; i++)
  {
    in>>vec[i].g >> vec[i].v;
  }
//  sort(vec.begin(),vec.end(),Comp());
//  for(auto it :vec)
  //  cout<<it.first<<' '<<it.second<<'\n';
  DP();
  return 0;
}