#include <cstdio>

#define GMAX 1001
#define WMAX 5001

int a[2][GMAX], G, W;
int c[GMAX], e[GMAX];

int main()
{
    int i, j, cap, l, sume, sumc;

    freopen("energii.in", "r", stdin);
    freopen("energii.out", "w", stdout);

    scanf("%d %d", &G, &W);
    sume = 0;
    sumc = 0;

    for(i=1;i<=G;++i)
    {
        scanf("%d %d", &e[i], &c[i]);
        sume += e[i];
        sumc += c[i];
    }

    cap = sume - W;

    for(i=1,l=1;i<=G;++i,l=1-l)
    {
        for(j=0;j<=cap;++j)
        {
            a[l][j] = a[1-l][j];

            if(e[i] <= j)
            {
                if(a[l][j] < a[1-l][j - e[i]] + c[i])
                {
                    a[l][j] = a[1-l][j - e[i]] + c[i];
                }
            }
        }
    }

    printf("%d", sumc - a[1-l][cap]);

    return 0;
}