#include <stdio.h>
#define inf 1000000000

long n,i,j,w,e[1003],c[1003];
long a[5003],b[5003],cmin[5003],ctmin;

int main(){
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    
    scanf("%ld",&n);
    scanf("%ld",&w);
    for (i=1;i<=n;i++)
        scanf("%ld %ld",&e[i],&c[i]);
    
    for (i=1;i<=w;i++)
        cmin[i]=inf;
    ctmin=inf;
    
    for (i=1;i<=n;i++){
        for (j=1;j<=w;j++)b[j]=0;
        if (e[i]<w){
           if (c[i]<cmin[e[i]]){cmin[e[i]]=c[i];b[e[i]]=1;}
        }
        else if(c[i]<ctmin)ctmin=c[i];
        
        for (j=1;j<=w;j++)
            if (a[j]>0){
               if (j+e[i]<w){
                  if (cmin[j]+c[i]<cmin[j+e[i]])
                     {cmin[e[i]+j]=cmin[j]+c[i];b[e[i]+j]=1;}
               }
               else if (cmin[j]+c[i]<ctmin)ctmin=cmin[j]+c[i];
            }
        for (j=1;j<=w;j++)a[j]=b[j];
    }
    printf("%ld\n",ctmin);
    
    return 0;
}