#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN=5001;
int d[MAXN];
int main()
{
    FILE *fin, *fout;
    int g,w,c,e,i,j,emax,minim;
    fin=fopen("energii.in","r");
    fout=fopen("energii.out","w");
    fscanf(fin,"%d\n%d\n",&g,&w);
    d[0]=1;
    minim=MAXN;
    emax=0;
    for(i=0;i<g;i++){
        fscanf(fin,"%d %d\n",&e,&c);
        for(j=emax;j>=0;j--)
            if(d[j]){
                if(j+e<w){
                    if(d[j+e]==0)   d[j+e]=d[j]+c;
                    else   d[j+e]=min(d[j+e],d[j]+c);
                    emax=max(emax,j+e);
                }
                else{
                    //printf("%d %d %d\n",j+e,d[j]+c,d[w]);
                    if(d[w]==0)   d[w]=d[j]+c;
                    else   d[w]=min(d[w],d[j]+c);
                    minim=min(minim,d[w]);
                    emax=max(emax,w);
                }
            }
    }
    fprintf(fout,"%d\n",minim-1);
    fclose(fin);
    fclose(fout);
    return 0;
}