#include<stdio.h>
#include<string.h>
#define maxl 200
long L,n;
long sal[maxl+1][maxl+1];
long v[101][2];

long sol(long a)
{
long i,k,j,l;
memset(sal,0,sizeof(sal));
sal[0][0]=1;
for(k=1;k<=n;k++)
  {
  for(i=L;i>=0;i--)
    {
    for(j=L;j>=0;j--)
	{
	if(sal[i][j])
	  for(l=0;l*v[k][0]<=a;l++)
	    {
	    sal[i+l][j+(a-l*v[k][0])/v[k][1]]=1;
	    if(i+l>=L && j+(a-l*v[k][0])/v[k][1]>=L)
		return 1;
	    }

	}

    }
  }
return 0;

}

long cauta(long a,long b)
{
if(a==b) return a;
long mij=(a+b)/2;
if(sol(mij)) return cauta(a,mij);
else return cauta(mij+1,b);

}



int main()
{
long x,i;

freopen("lapte.in","rt",stdin);
//freopen("lapte.out","wt",stdout);

scanf("%ld%ld",&n,&L);
for(i=1;i<=n;i++)
  scanf("%ld%ld",&v[i][0],&v[i][1]);
x=cauta(1,L);
printf("%ld\n",x);



return 0;
}