Problem E: 最大值Reserved
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：9
Solved：7
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张大小相同的正方形,正方形的边长最大是多少(裁剪的正方形边长必须为整数).
例如: N=2, 有2张彩纸，第一张彩纸W=4,H=3, 第二张彩纸W=5,H=4, K=6, 裁剪的6个正方形边长最大是2.
当给出N张长方形彩纸W和H, 及K的值, 请计算出将N张彩纸裁剪出K张大小相同的正方形,正方形的边长最大是多少(裁剪的正方形边长必须为整数).
Input
输入分为N+1行, 第一行为正整数N(1<N<500), 表示彩纸数量;
以下n行每行有两个正整数W和H, 表示每张彩纸的宽和高, 整数之间用一个空格隔开; W和范围在1和10000之间
最后一行为正整数K(1<K<500), 表示要剪成的正方形数.
以下n行每行有两个正整数W和H, 表示每张彩纸的宽和高, 整数之间用一个空格隔开; W和范围在1和10000之间
最后一行为正整数K(1<K<500), 表示要剪成的正方形数.
Output
输出一个整数，表示正方形的边长最大是多少.
Sample Input Copy
2
4 3
5 4
6Sample Output Copy
2