题目背景
手工课上拿同学出N张长方形彩纸,且每张彩纸上都画着W * H的网格(网格铺满整张彩纸)。现在同学将N张彩纸裁剪出K张大小相同的正方形,并且要使裁剪出的正方形的边长最大(裁剪的正方形边长必须为整数)。
例如:N=2, 有2张彩纸,第一张彩纸W = 4, H = 3:第二张彩纸W = 5,H = 4; K = 6,裁剪的6个正方形边长最大是2。
当给出N张长方形彩纸W和H,及K的值,请计算出将N张彩纸裁剪出K张大小相同的正方形,正方形的边长最大是多少(裁剪的正方形边长必须为整数)。
输入格式
第一行输入两个正整数N,K(1<N<100,1<K<100), N表示彩纸数量,K表示需裁剪的正方形数量,两个正整数之间一个空格隔开. 第二行开始,输入N行,每行输入两个正整数Wi,Hi (1 < Wi < 1000,1 < Hi < 1000,且 Wi≠Hi,,Wi表示彩纸的长度,Hi表示彩纸的宽度,两个正整数之间一个空格隔开.
**输出格式
**
输出一个正整数,表示将N张彩纸裁剪出K张大小相同的正方形的边长最大是多少(裁剪的正方形边长必须为整数),如果不能裁剪出K张正方形就输出“-1”
输入输出样例
输入样例
2 6
4 3
5 4
输出样例
2