题目描述

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

例如: N=2, 有2张彩纸，第一张彩纸W=4,H=3, 第二张彩纸W=5,H=4, K=6, 裁剪的6个正方形边长最大是2.

输入格式

输入分为N+1行, 第一行为正整数N(1<N<500), 表示彩纸数量;

以下n行每行有两个正整数W和H, 表示每张彩纸的宽和高, 整数之间用一个空格隔开;

最后一行为正整数K(1<K<500), 表示要剪成的正方形数.

输出格式

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

样例

样例输入1

2
4 3
5 4
6

样例输出1

2