#include<stdio.h>
#define INF 2000000000
int w[5002];
int main(){
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    int n,wmin,g,e,smax=0;
    scanf("%d%d",&n,&wmin);
    w[0]=0;
    for(int i=1;i<=5001;i++){
        w[i]=INF;
    }
    for(int i=1;i<=n;i++){
        scanf("%d%d",&e,&g);
        for(int j=smax;j>=0;j--){
            if(w[j]!=INF){
                if(j+e>=wmin){
                    if(w[j+e]<w[wmin]){
                        w[wmin]=w[j]+g;
                    }
                }
                else{
                    if(w[j+e]>w[j]+g){
                        w[j+e]=w[j]+g;
                    }
                }
            }
        }
        smax=smax+e;
        if(smax>wmin){
            smax=wmin;
        }
    }
    printf("%d\n",w[wmin]);
    return 0;
}