#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1001;

struct gen{
    int energie;
    int cost;
};

gen g[N];

bool cmp(gen a, gen b){
    if(a.energie == b.energie)
        return (a.cost < b.cost);
    return (a.energie < b.energie);
}

int castig[1001],cost[1001],mat[3][10000001];

int maxim(int x,int y){
    if(x > y)
        return x;
    return y;
}

int main(){
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    int x, y, s = 0, i, j, gn, w, min = 99999999, sol;
    scanf("%d%d",&gn,&w);
    // citire
    for(i = 1; i <= gn; i++){
        scanf("%d%d",&g[i].energie,&g[i].cost);
        s += g[i].energie;
    }
    // linia 1
    sort(g + 1, g + gn + 1, cmp);
    for(i = 0; i <= s; i++)
        mat[1][i] = g[1].cost;
    // rucsac
    bool pp = false;
    for(i = 2; i <= gn; i++){
        for(j = 1; j <= s && pp == false; j++){
            mat[2][j] = maxim(mat[1][j], mat[1][j-g[i].energie]+g[i].cost);
            if(mat[2][j] >= w){
                pp = true;
                i = gn + 2;
                printf("%d",mat[2][j]);
            }
        }
        for(j = 1;j <= s; j++)
            mat[1][j]=mat[2][j];
    }
    return 0;
}