880051 - 最大值
时间限制 : 1 秒
内存限制 : 128 MB
手工课上, 老师拿出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+1行, 第一行为正整数N(1<N<500), 表示彩纸数量; 以下n行每行有两个正整数W和H, 表示每张彩纸的宽和高, 整数之间用一个空格隔开; 最后一行为正整数K(1<K<500), 表示要剪成的正方形数.
输出
输出一个整数,表示正方形的边长最大是多少.
样例
输入
2 4 3 5 4 6
输出
2