#include <bits/stdc++.h>

using namespace std;

ifstream F("energii.in");
ofstream G("energii.out");

int n, m, e1, c1, e[5003], c[5003], d[3][5002], k;
const int inf = 1<<30;

int main()
{
    F >> n >> m;
    for( int i = 1; i <= n; ++ i )
    {
        F >> e1 >> c1;
        if( e1 > m )
        {
            e[ m ] = min( e[ m ], e1 );
            c[ m ] = min( c[ m ], c1 );
        }
        else
        {
            e[ ++ k ] = e1;
            c[ k ] = c1;
        }
    }
    for( int i = 1; i <= m; ++ i )
    {
        d[ 0 ][ i ] = inf;
    }
    for( int i = 1; i <= k; ++ i )
    {
        if( i % 2 )
        {
            for( int j = 1; j <= m; ++ j )
            {
                if( j <= e[ i ] )
                {
                    d[ 1 ][ j ] = min( d[ 0 ][ j ] , c[ i ] );
                }
                else
                {
                    d[ 1 ][ j ] = min(  d[ 0 ][ j ] , d[ 0 ][ j - e[i] ] + c[ i ]  );
                }
            }
            continue;
        }
        for( int j = 1; j <= m; ++ j )
        {
            if( j <= e[ i ] )
            {
                d[ 0 ][ j ] = min( d[ 1 ][ j ] , c[ i ] );
            }
            else
            {
                d[ 0 ][ j ] = min(  d[ 1 ][ j ] , d[ 1 ][ j - e[i] ] + c[ i ]  );
            }
        }
    }
    G << d[ 1 ][ m ];
    return 0;
}