#include <fstream>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int smax=10000;
const int inf=1e9;
const int nmax=5000;
int nr[nmax+1],co[nmax+1],costper[smax+1];

int main()
{
    int s,n;
    in>>n>>s;
    for(int i=1; i<=s*2; i++)
    {
        costper[i]=-inf;
    }
    costper[0]=0;
    for(int i=1; i<=n; i++)
    {
        in>>nr[i]>>co[i];
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=s-nr[i]; j>=0; j--)
        {
            if(co[i]+costper[j]<costper[j+nr[i]])
                costper[j+nr[i]]=co[i]+costper[j];
        }
    }
    int max=inf;
    for(int i=0; i<=s*2; i++)
    {
        if(costper[i]<max)
        max=costper[i];
    }
    out<<max;
    return 0;
}