#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");

int N,G,DP[5005][10010],c[10005],w[10005];

void Read()
{
    fin>>N>>G;
    for(int i=1;i<=N;++i)
        fin>>w[i]>>c[i];
}

void Solve()
{
    int l=0;
    for(int i=1;i<=N;++i,l=1-l)
        for(int j=1;j<=G;++j)
            {DP[1-l][j]=DP[1][j];
            if(w[i]<=j)
                DP[1-l][j]=min(DP[i-1][j],c[i]+DP[i-1][j-w[i]]);
            }
    fout<<DP[1][G];
}

int main()
{
    Read();
    Solve();
    return 0;
}