#include <fstream>
#define inf (1 << 30)
using namespace std;

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

int n, i, j;
long long sol;
long long a[10001];
int w, e, c;

int main()
{
    f >> n >> w;
    for (i = 0; i < n; i++)
    {
        f >> e >> c;
        int minim = max(w-e-1, 0);
        sol = inf;
        for (j = w-1; j >= minim; j--)
            if (a[j] != inf)
                sol = min(sol, a[j]+c);

        for (j = w-e-1; j >= 0; j--)
            if (a[j] != inf)
            {
                if (a[j+e] < a[j]+c)
                    a[j+e] = a[j]+c;
            }

    }

    g << sol;
    return 0;
}