#include <stdio.h>
#define MAXINT 10000
int Energie[3][1000],i,j,N,G,cost_min[3][10000];
int reactor[10000],cost[10000];

int max(int a,int b) {
    if(a>b) return a;
    else    return b;
}

int verifica(int a,int b) {
    if(b<0) return 0;
    else return Energie[a][b];
}

int min(int a,int b) {
    if(a<b) return a;
    else    return b;
}

void afis() {
     int i,j;
     for(i=0;i<=N;i++) {
         for(j=0;j<=G;j++)
             printf("%d ",cost_min[i][j]);
         printf("\n\n");
     }
}

int main() {

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

     scanf("%d",&N);
     scanf("%d",&G);

     for(i=1;i<=N;i++) { scanf("%d",&reactor[i]); scanf("%d",&cost[i]); }
     
     for(i=0;i<=1;i++) Energie[i][0]=1; // am modificat "n"

     for(i=1;i<=N;i++)
         for(j=1;j<=2*G;j++) {
             Energie[i%2][j] = max( verifica((i-1)%2,j-reactor[i]) , Energie[(i-1)%2][j] );
             cost_min[i%2][j]=MAXINT;
             if(Energie[i%2][j]) {
                if(verifica((i-1)%2,j-reactor[i])) cost_min[i%2][j]=min(cost_min[(i-1)%2][j-reactor[i]]+cost[i] , cost_min[i%2][j]);
                cost_min[i%2][j]= min(cost_min[i%2][j],cost_min[(i-1)%2][j]);
             }
         }
         
     printf("%d",cost_min[N%2][G]);

     return 0;
}