You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Mibbp去新疆玩，正好看到路边有人再卖切糕，Mibbp买了N块切糕请他的K个朋友吃，

其中第 i 块是 H_i×W_i 的方格组成的长方形。

为了公平起见，Mibpp需要从这N块切糕切出K块切糕分给他的朋友

切出的切糕需满足：

• 必须是单个完整的不能拼凑

• 形状是正方形，边长为整数

• 大小相同

比如一块6×5的切糕可以切出6块2×2的切糕或者2块3×3的切糕

当然Mibbp的朋友们肯定希望能得到的切糕尽可能的大，你能帮Mibpp计算出最大的边

长是多少吗。

输入格式

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

以下 N行每行包含两个整数 H_i 和 W_i。

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

输出格式

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

数据范围

1≤N,K≤${10^5}$,1≤H_i,W_i≤${10^5}$

2 10
6 5
5 6

2