#include<stdio.h>
#include<fstream.h>
#define nmax 30

int l,va[nmax],vb[nmax],n,min[nmax][nmax],min1[nmax][nmax];
inline int minim(int a, int b) {return a>b?a:b;}
int rezolva();

int main()
{int i;
freopen("lapte.in","r",stdin);
 scanf("%d%d",&n,&l);
 for(i=1;i<=n;i++)
  scanf("%d%d",&va[i],&vb[i]);
 freopen("lapte.out","w",stdout);
 printf("%d",rezolva());
 fclose(stdout);
 return 0;
 }
void initializare()
{int i,j;
 for(i=0;i<=l;i++)
  for(j=0;j<=l;j++)
	min1[i][j]=vb[1]*j+va[1]*i;
 }
void init1(int a,int b)
{int i;
 for(i=0;i<=b;i++)
	min[i][0]=minim(va[a]*i,min1[b-i][0]);

 }

int rezolva()
{int i,j,k1,k2,d,c;
 initializare();
 for(i=2;i<=n;i++)
   {for(k1=0;k1<=l;k1++)
	  {init1(i,k1);
	   for(k2=1;k2<=l;k2++)
		  {for(d=1,c=min1[0][k2]+k1*va[i];d<=k2;d++)
			 c=minim(c,min1[i][k2]+(k1-d)*va[i]);

		   min[k1][k2]=minim(min[k1][k2-1]+vb[i],c);
		   }
	   }
   memcpy(min1,min,sizeof(min));

   }
 return min[l][l];
 }