2485: LQ1156 裁剪的最大值 省赛
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:1
Description
手工课上老师拿出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张大小相同的正方形,正方形的边长最大是多少(裁剪的正方形边长必须为整数)。
Input
第一行输入两个正整数N,K(1<N<100,1<K<100),N表示彩纸数量,K表示需裁剪的正方形数量,两个正整数之间一个空格隔开。
第二行开始,输入N行,每行输入两个正整数Wi,Hi(1<Wi<1000,1<Hi<1000,且Wi!=Hi),Wi表示彩纸的长度,Hi表示彩纸的宽度,两个正整数之间一个空格隔开。
Output
输出一个正整数,表示将N张彩纸裁剪出K张大小相同的正方形的边长最大是多少(裁剪的正方形边长必须为整数),如果不能裁剪出K张正方形就输出“-1"。
Sample Input Copy
2 6
4 3
5 4
Sample Output Copy
2