No submission language available for this problem.

Background

时空管理局本期的选拔终于告一段落，A 也顺利地通过了选拔，与其他人共 k 人成为了时空管理员。

Description

时空管理局拿出 n 个长方形蛋糕准备庆祝，为了方便问题的描述，第 i 个蛋糕的尺寸为 $H_i$ × $W_i$ 。为了公平起见，管理局希望从这 n 个长方形的蛋糕中，切出 k 块蛋糕给到所有人。切出的蛋糕需要满足：

• 大小是相同的
• 都是正方形，且边长是整数

例如一块 6 × 6 的蛋糕，可以切出 9 块 2 × 2 的蛋糕或 4 块 3 × 3 的蛋糕。

Format

Input

第一行包含两个整数 n 和 k 分别表示蛋糕的数量和庆祝的人。

之后的 n 行每行包含两个整数 $H_i$ 和 $W_i$

Output

输出切出的正方形蛋糕最大可能的边长

Samples

2 10
6 5
5 6

2

Limitation

1 ≤ n, k ≤ 100000

1 ≤ $H_i$, $W_i$ ≤ 100000