地主有n块土地，其中第i块是ci×ri的方格组成的长方形。他雇k位农民种地。

农民工作量要相同，否则他们就不干活。地主需要从这n块地中圈出k块正方形土地给农民，这k块正方形土地，大小相同，且边长是整数。

例如一块7×4的土地可以圈出 6块2×2的土地 或者 2块3×3的土地。

地主希望尽可能多的土地能被耕种，请你帮他找到最大的边长。

输入

第一行包含两个整数n和k。(1≤n,k≤10^5)。

以下n行，每行包含两个整数ci和ri。(1≤ci,ri≤10^5)。

输入保证每个农民至少种1×1的土地，否则就浪费地主发出的工资了。

输出

最大可能的边长。

例子

输入

2 10

6 5

5 6

输出

2

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,c[100005],r[100005],minn=1000000,s; 
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>c[i]>>r[i],minn=min(minn,min(c[i],r[i]));
	s=minn;
	while(1){
		ll t=0;
		for(int i=1;i<=n;i++)
		{
			t+=(c[i]/s)*(r[i]/s);			
		}
		if(t>=k){
		    cout<<s;
		    return 0;
		}
		s--;
	}

	return 0;
}

20分悬关QWQ