#include <fstream>

using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");

int e,p,w,n,i,j,ec;
int a[5010],b[5010];

int main()
{
    fin>>n>>w; ec=100000;
    for(i=1;i<=n;i++)
    {
        fin>>e>>p;
        for(j=1;j<w;j++)
            a[j]=b[j],b[j]=0;

        if(e>=w)
        {
            if(p<ec)
                ec=p;
        }
        else b[e]=p;
        for(j=1;j<w;j++)
        {
            if(a[j]!=0)
            {

                if(a[j]<b[j] || b[j]==0)
                    b[j]=a[j];

                if(j+e>=w && a[j]+p<ec)
                    ec=a[j]+p;

                if(j+e<w)
                    b[j+e]=a[j]+p;
            }
        }
    }
    fout<<ec;
    return 0;
}