手工课上老师拿出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"