题目描述

1024那天有 K 位ACM队员到syl家做客。

syl拿出了珍藏的小蛋糕招待他们。

syl一共有 N 块小蛋糕，其中第 i 块是 Hi×Wi 的方格组成的长方形。

为了公平起见，syl需要从这 N 块小蛋糕中切出 K 块小蛋糕分给朋友们。

切出的小蛋糕需要满足：

形状是正方形，边长是整数 大小相同 例如一块 6×5 的小蛋糕可以切出 6 块 2×2 的小蛋糕或者 2 块 3×3 的小蛋糕。

当然小朋友们都希望得到的小蛋糕尽可能大，你能帮syl计算出最大的边长是多少么？

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行包含两个整数 Hi 和 Wi。

输入保证每位小朋友至少能获得一块 1×1 的小蛋糕。

输出格式

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

样例

输入样例

2 10
6 5
5 6

输出样例

2

数据范围与提示

1≤N,K≤1e5, 1≤Hi,Wi≤1e5