#include <iostream>
#include <fstream>
#define INF 1000000000
using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");
int n,w,v[5005];
int main()
{
    fin>>n>>w;
    for(int i=1;i<=w;i++)
        v[i]=INF;
    for(int i=1;i<=n;i++) {
        int x,y;
        fin>>x>>y;
        for(int j=w;j>=0;j--) {
            int next=j+x;
            if(next>w)
                next=w;
            v[next]=min(v[j]+y,v[next]);
        }
    }
    fout<<v[w];
    return 0;
}