小明分巧克力问题

一、问题描述

儿童节当天，有 $K$ 位小朋友到小明家做客，小明打算用珍藏的巧克力来招待他们。小明共有 $N$ 块巧克力，其中第 $i$ 块是由 $H_i\times W_i$ 的方格组成的长方形。

小明需要从这 $N$ 块巧克力中切出 $K$ 块分给小朋友，且切出的巧克力要满足以下条件：

1. 形状为正方形，且边长为整数；
2. 所有切出的巧克力大小相同。

例如，一块 $6\times5$ 的巧克力，可以切出 $6$ 块 $2\times2$ 的巧克力或者 $2$ 块 $3\times3$ 的巧克力。小朋友们都希望得到的巧克力尽可能大，现在请你帮忙计算出切出的正方形巧克力的最大可能边长。

二、输入描述

• 第一行：包含两个整数 $N$ 和 $K$（$1\leq N, K\leq 10^5$）。
• 接下来 $N$ 行：每行包含两个整数 $H_i$ 和 $W_i$（$1\leq H_i, W_i\leq 10^5$）。

输入保证每位小朋友至少能获得一块 $1\times1$ 的巧克力。

三、输出描述

输出一个整数，表示切出的正方形巧克力的最大可能边长。

四、输入输出样例

输入

2 10
6 5
5 6

输出

2

五、数据规模分档

• 对于 $30\%$ 的数据：$N\leq 100$，$K\leq 100$，$1\leq H_i, W_i\leq 100$；
• 对于 $70\%$ 的数据：$N\leq 10000$，$K\leq 10000$，$1\leq H_i, W_i\leq 10000$；
• 对于 $100\%$ 的数据：$1\leq N, K\leq 10^5$，$1\leq H_i, W_i\leq 10^5$ 。