#include <iostream>
#include <fstream>

using namespace std;

ifstream f("energii.in");
ofstream g("energii.out");

int x, y;
int n, w, i, j, minim = 1e9;
int a[3][5005+10005];

int main()
{
    //cout << sizeof(a) / (1024.0D * 1024.0D);

    f >> n >> w;

    for(i = 1; i <= n; i ++)
    {
        f >> x >> y;

        for(j = 1; j <= w; j ++) {a[1][j] = a[2][j];}

        for(j = 0; j <= w; j ++)
        {
            if( (a[1][j] != 0 || j == 0) && (a[1][j] + y < a[1][j+x] || a[1][j+x] == 0) )
            {
                a[2][j+x] = a[1][j] + y;
            }
            if(j+x >= w && a[2][j+x] > 0)
                {
                    if(a[2][j+x] < minim)
                    {
                        minim = a[2][j+x];
                    }
                }
        }

    }

    g << minim;

    f.close();
    g.close();
    return 0;
}