手工课上, 老师拿出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), 表示要剪成的正方形数.

输出一个整数，表示正方形的边长最大是多少.