#4677. 最大值(2022年4月省赛第一场)

最大值(2022年4月省赛第一场)

Background

最大值

题目描述:

手工课上老师拿出N张长方形彩纸,且每张彩纸上都画着W*H的网格(网格铺满整张彩纸)。现在老师将N张彩纸裁剪出K张大小相同的正方形,并且要使裁剪出的正方形的边长最大(裁剪的正方形边长必须为整数)。

例如:N=2,有2张彩纸,第一张彩纸W=4,H=3;第二张彩纸W=5,H=4;K=6,裁剪的6个正方形边长最大是2。 image 当给出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

评分标准:

10分:能正确输出一组数据;

10分:能正确输出两组数据;

20分:能正确输出三组数据;

20分:能正确输出四组数据。

Limitation

1s, 1024KiB for each test case.