#include <iostream>
#include <fstream>
#define min(A,B) (A>B)?(B):(A)
#define change(A) (A%2==1)?0:1

using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
struct generator
{
    int cost;
    int energie;
};
int g,w;
generator listaItemi[1010];
int memo[2][5010];

int main()
{
    fin>>g>>w;
    for(int i = 1; i<=g; i++)
        fin>>listaItemi[i].energie>>listaItemi[i].cost;

    for(int i = 1;i<=g;i++)
    {
        for(int j = 0;j<=w;j++)
        {
            if(j>=w)
                memo[i%2][j] = 0;
            else if(i==1)
                memo[i%2][j] =  1000000000;
            else
                memo[i%2][j] = min(listaItemi[i].cost + memo[change(i)][min(j+listaItemi[i].energie,w)],memo[change(i)][j]);
        }
    }

    fout<<memo[g%2][0];
    return 0;
}