#include<cstdio>
#include<cstring>
const int maxn=105;
int n,m,a[maxn],b[maxn],f[maxn][maxn];
void _max(int &x,int y){if(x<y)x=y;}
bool _judge(int sb){
	memset(f,-1,sizeof(f));
	int tot=0,i,j,k;
	for(i=1;i<=n;i++)tot+=sb/b[i],f[i][0]=tot;
	f[0][0]=0;//注意可能上一个for循环得数都是0 
	for(i=1;i<=n;i++)
	for(j=0;j<=m;j++)
	for(k=0;k<=j;k++)
		if(k*a[i]<=sb)//负数 
		if(f[i-1][j-k]>-1)
			_max(f[i][j],f[i-1][j-k]+(sb-k*a[i])/b[i]);
	if(f[n][m]>=m)return true;
	return false;
}
int main(){
	freopen("time.in","r",stdin);freopen("time.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	int l=1,r=a[1]*m+b[n]*m,mid;
	while(l^r){
		mid=(l+r)>>1;
		if(_judge(mid))r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	fclose(stdin);fclose(stdout);
}