#include<fstream>
#include<cstring>
#define INF 50000001
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int min(int a,int b){
    if(a>b)
        return b;
    else
        if(b>a)
            return a;
        if(b==a)
            return a;
}
int n,w,i,j,sol,maxim;
int W[5003],d[100001],C[5003];
int main(){
    fin>>n>>w;
    for(i=1;i<=n;i++) {
        fin>>W[i]>>C[i];
    }
    for(i=1;i<=w;i++)
        d[i]=INF;
    d[0]=0;
    for(i=1;i<=n;i++){
        for(j=w;j>=0;j--)
            if(d[j]!=INF) {
                if(j+W[i]>w) {
                    d[w]=min(d[w],d[j]+C[i]);
                }else{
                    d[j+W[i]]=min(d[j+W[i]],d[j]+C[i]);
                }
            }
    }
    fout<<d[w];
    return 0;
}