#include <fstream>
#include <cstring>

using namespace std;

const int NMAX = 1001 ;
const int CMAXA = 10001 ;
const int INF = 0x3f3f3f3f;

ifstream cin("energii.in") ;
ofstream cout("energii.out") ;

int N, P;
int G[NMAX];
int W[NMAX];
int CMax[CMAXA] ;
int sol;

inline int max(int a, int b)
{
    if(a > b) return a ;
    else return b ;
}

inline void Rezolvare()
{

    //memset(CMax, INF, sizeof(CMax)) ;

for(int h = 1 ; h <= P + NMAX ;  ++ h )
        CMax[h] = INF ;

    for(int i = 1 ; i <= N ; ++ i)
    {
        int a, b;
        cin >> a >> b;
        for(int s = P; s >= 0  ; -- s)
            if(CMax[s] + b < CMax[s + a])
                CMax[s + a] = CMax[s] + b ;


    }

}

int main()
{


    cin >> N;
    cin >> P ;

sol = INF ;

    Rezolvare();
    for(int i = P ; i <= P + NMAX ; ++ i) if(CMax[i] < sol) sol = CMax[i] ;
    cout << sol << '\n' ;
    cin.close();
    cout.close();
    return 0;
}