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

const int N_max = 1000;
const int G_max = 5000;
const int cost_max = 10000;
const int INF = 100000007;

int cost[G_max+cost_max+1];
int g[N_max+1], p[N_max+1];

int N, G;

int main()
{
    freopen("energii.in", "r", stdin);
    freopen("energii.out", "w", stdout);

    int i, j;

    scanf("%d %d", &N, &G);
    for(i = 1; i <= N; i++) scanf("%d %d", &g[i], &p[i]);

    for(i = 1; i <= G; i++) cost[i] = INF;

    cost[0] = 0;

    for(i = 1; i <= N; i++)
        for(j = G + g[i]-1; j >= g[i]; j--)

            if(cost[j - g[i]] != INF)
            {
                if(j >= G)
                    if(cost[j - g[i] ] + p[i] < cost[G])
                        cost[G] = cost[j - g[i]] + p[i];
                    else ;
                else
                    if(cost[j - g[i] + p[i] < cost[j]])
                        cost[j] = cost[j - g[i]] + p[i];
            }

    printf("%d", cost[G]);

    return 0;
}