#include<bits/stdc++.h>
using namespace std;
int n,k,h[100000],w[100000],sum,ans,b;
int a(int hi,int wi,int i){//函数a：计算这块巧克力可以切出出多少块i*i的巧克力
    if(hi>=i&&wi>=i){//如果巧克力的边长都大于等于i
        b+=((hi-hi%i)/i)*((wi-wi%i)/i);//计算这块巧克力能切出多少块i*i的巧克力
    }
    return b;//返回b
}
int main(){
    cin>>n>>k;//输入巧克力的数量和小朋友的人数
    for(int i=1;i<=n;i++){//循环巧克力的块数次
        cin>>h[i]>>w[i];//输入这块巧克力的长（h[i]）和宽（w[i]）
        sum+=h[i]*w[i];//sum＋这块巧克力的面积
    }
    sum=sum/k;//平均每个小朋友分到sum块巧克力
    for(int i=1;i<=sum;i++){//循环直到每个小朋友分到的巧克力块数达到最多
        b=0;//将b清零
        for(int j=1;j<=n;j++){//循环巧克力的块数次
        	int hi=h[i],wi=w[i];//因为h[i],w[i]进不了函数，就先赋值一下
            b+=a(hi,wi,i);//使用函数，计算这块巧克力可以切出出多少块i*i的巧克力
        }
        if(b>=k){//如果切出来的巧克力块数<或=小朋友的数量
            ans=max(ans,i);//如果i>ans，将答案（ans）设为i
        }
        if(b<k){//如果切出来的巧克力的数量比小朋友的数量还少
            break;//跳出循环
        }
    }
    cout<<ans;//输出切出巧克力正方形的最大边长
	return 0;
}