#include <cstdio>
#define DIM 5005
#define INFI 0x3f3f3f3f
using namespace std;

int v[DIM];
int c[DIM], e[DIM];

int minim( int a, int b ){
    if( a < b ) return a;
    return b;
}

int main()
{

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

    int n, i, j, s, t, d, k, w;

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

    for( i = 1; i <= DIM; ++i )
        v[i] = INFI;

    for( i = 1; i <= n; ++i ){
        for( j = w - 1; j >= 0; --j ){
            if( j + e[i] <= w ){
                if( v[j] != INFI && v[j] + c[i] < v[j+e[i]] )
                    v[j+e[i]] = v[j] + c[i];
            }
            else v[w] = minim( v[w], j + e[i] );
        }
    }

    printf("%d",v[w]);


    return 0;
}