///circular
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int i,j,n,g,ras[5][5010],mi=INT_MAX;
struct ceva
{
    int e,c;
} gen[1010];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fin>>n>>g;
    for(i=1; i<=n; i++)
        fin>>gen[i].e>>gen[i].c;
    for(i=1; i<=g+1; i++)
        ras[0][i]=ras[1][i]=INT_MAX-10010;
    int c=1;
    for(i=1; i<=n; i++)
    {
        for(j=0; j<=g; j++)
        {
            if(j+gen[i].e>g)
                ras[c][g+1]=min(ras[1-c][j]+gen[i].c,ras[c][g+1]);
            if(gen[i].e<=j)
                ras[c][j]=min(ras[1-c][j],ras[1-c][j-gen[i].e]+gen[i].c);
            else
                ras[i][j]=ras[1-c][j];
        }
        mi=min(mi,min(ras[c][g],ras[c][g+1]));
        c=1-c;
    }
    fout<<mi;
    return 0;
}