#include <cstdio>

using namespace std;
FILE *f,*g;

struct bla
{
    int gr,pr;
}v[5002];
int cost[4][10002];

int main()
{
    f=fopen("rucsac.in","r");
    g=fopen("rucsac.out","w");
    int n,G;
    fscanf(f,"%d %d",&n,&G);
    for(int i=1;i<=n;++i)
        fscanf(f,"%d %d",&v[i].gr,&v[i].pr);
    int lc=1,lp=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=G;++j)
            if(v[i].gr<=j)
            {
                if(cost[lp][j]>cost[lp][j-v[i].gr]+v[i].pr)
                    cost[lc][j]=cost[lp][j];
                else
                    cost[lc][j]=cost[lp][j-v[i].gr]+v[i].pr;
            }
            else
                cost[lc][j]=cost[lp][j];
        lc^=1;
        lp^=1;
    }
    fprintf(g,"%d",cost[lp][G]);
    fclose(f);
    fclose(g);
    return 0;
}