#include <cstdio>
#include <algorithm>

using namespace std;

struct poz
{
    int g,c;
}v[1006];

int a2b[160002];

bool cmp(poz a,poz b)
{
    if (a.c < b.c) return 1;
    return 0;
}

int main()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    int G,W;
    scanf("%d %d",&G,&W);
    for (int i=1;i<=G;i++)
        scanf("%d %d",&v[i].g,&v[i].c);
    sort(v+1,v+G+1,cmp);
    for (int i=1;i<=W;i++) a2b[i]=2100000000;
    a2b[0]=0;
    for (int i=1;i<=G;i++)
    {
        for (int j=W;j>=0;j--)
        {
            if (j+v[i].g<=W && a2b[j+v[i].g]>a2b[j]+v[i].c) a2b[j+v[i].g]=a2b[j]+v[i].c;
            if (j+v[i].g>=W && a2b[W]>a2b[j]+v[i].c) a2b[W]=a2b[j]+v[i].c;
        }
    }
    printf("%d ",a2b[W]);
}