#include<cstdio>
#include<set>
using namespace std;
set<int> cd;
set<int>::reverse_iterator it;
int i, cd2[10005], a[10005], n, m, val, c, mn, x;
int main(){
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    scanf("%d%d", &n, &m); for (i=1;i<=2*m;i++) a[i]=999999999;
    a[0]=0; cd2[0]=0; cd.insert(0); mn=999999999;
    for (i=1;i<=n;i++) {
        scanf("%d%d", &val, &c);
        for (it=cd.rbegin();it!=cd.rend();it++) {
            x=*it;
            if ((x<m)&&(a[x+val]>x+c)) {
                if (a[x+val]==999999999) cd2[++cd2[0]]=x+val;
                a[x+val]=x+c;
                if ((x+val>=m)&&(a[x]+c<mn)) mn=a[x]+c;
            }
        }
        for (c=1;c<=cd2[0];c++) cd.insert(cd2[c]);
    }
    printf("%d\n", mn); return 0;
}