#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, masa,obiecte[5001], pret[5001];
int d[10001];

void citire()
{
    fin >> n >> masa;
    for(int i = 0; i < n; ++i)
        fin >> obiecte[i] >> pret[i];
}

int minim()
{
    for(int i = 0; i < n; ++i)
        for(int j = masa; j > 0 && j - obiecte[i] >= 0; --j)
        {
            if(d[j]> d[j-obiecte[i]] + pret[i]) 
            d[j] = d[j];
            else
            d[j]=d[j-obiecte[i]] + pret[i];
        }

    return d[masa];
}

int main()
{
    citire();
    fout << minim();
    return 0;
}