#include <stdio.h>
#define INF 2000000000
#define MAXN 1000
#define MAXK 5000
int d[MAXN+1][MAXK+1];
int main(){
    int n, k, i, e, c, j, act, min;
    FILE *fin, *fout;
    fin=fopen("energii.in", "r");
    fout=fopen("energii.out", "w");
    fscanf(fin, "%d%d", &n, &k);
    for(i=0; i<=k; i++){
        d[0][i]=INF;
    }
    for(i=1; i<=n; i++){
        fscanf(fin, "%d%d", &e, &c);
        min=INF;
        for(j=k; j>0; j--){
            act=d[i-1][j];
            if((j>=e)&&(act>d[i-1][j-e]+c)){
                act=d[i-1][j-e]+c;
            }
            if(act<min){
                min=act;
            }
            d[i][j]=min;
        }
    }
    fprintf(fout, "%d\n", d[n][k]);
    fclose(fin);
    fclose(fout);
    return 0;
}