///circular
#include <bits/stdc++.h>
#define MOD 777013
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int i,j,n,w,v[5010],e[1010],c[1010];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fin>>n>>w;
    for(i=1; i<=n; i++)
        fin>>e[i]>>c[i];
    for(i=1; i<=w+1; i++)
        v[i]=INT_MAX-10010;
    for(i=1; i<=n; i++)
        for(j=w; j>=0; j--)
        {
            if(j+e[i]>w)
                v[w+1]=min(v[w+1],v[j]+c[i]);
            if(j>=e[i])
                v[j]=min(v[j],v[j-e[i]]+c[i]);
        }
    fout<<min(v[w],v[w+1]);
    return 0;
}