#include <cstdio>
#include <algorithm>
#define MAXN 1001
#define MAXC 10011001

using namespace std;
FILE *fin=fopen("energii.in","r"),*fout=fopen("energii.out","w");
int e[MAXN],c[MAXN],d[2][MAXC];
int main(){
    int n,et,s=0;
    fscanf(fin,"%d%d",&n,&et);
    for(int i=1;i<=n;i++){
        fscanf(fin,"%d%d",&e[i],&c[i]);
        s+=e[i];
    }
    int lin=0;
    for(int i=1;i<=n;i++,lin=1-lin){
        for(int ce=0;ce<=s;ce++){
            d[1-lin][ce]=d[lin][ce];
            if(e[i]<=ce){
                d[1-lin][ce]=max(d[1-lin][ce],d[lin][ce-e[i]]+c[i]);
            }
        }
    }
    int mincost;
    mincost=d[lin][et];
    for(int i=et+1;i<=s;i++){
        if((d[lin][i]<mincost and d[lin][i]!=0) or mincost==0)
            mincost=d[lin][i];
    }
    fprintf(fout,"%d",mincost);
    return 0;
}