#include <fstream>
#include <iostream>
#define OO 10000001
#define maxim 5008


using namespace std;

ifstream f("energii.in");
ofstream g("energii.out");


int n,G,l1,l2;
int ans[2][maxim];

struct
{
 int w,c;
}ob[maxim];


void citire()
{
    f>>n>>G;
    for (int i=1;i<=n;i++)
        f>>ob[i].w>>ob[i].c;
}

void reset()
{
    for (int i=1;i<=G;i++)
        ans[l1][i]=OO;
}




int main()
{
    citire();
    l1=0;
    l2=1;
    reset();
    for (int i=1;i<=n;i++)
      {
          for (int j=0;j<=G;j++)
            if (ob[i].w >= j)
                ans[l2][j]=min(ans[l1][j],ans[l1][j-ob[i].w]+ob[i].c);
            else ans[l2][j]=ans[l1][j];

         reset();
         swap(l1,l2);
      }
    if (n%2==0)
    g<<ans[0][G];
    else g<<ans[1][G];

    return 0;


}