分巧克力（整數二分）

兒童節那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友們。

小明一共有 N 塊巧克力，其中第 i 塊是 Hi×Wi 的方格組成的長方形。

為了公平起見，小明需要從這 N 塊巧克力中切出 K 塊巧克力分給小朋友們。

切出的巧克力需要滿足：

形狀是正方形，邊長是整數

大小相同

例如一塊 6×5 的巧克力可以切出 6 塊 2×2 的巧克力或者 2 塊 3×3 的巧克力。

當然小朋友們都希望得到的巧克力盡可能大，你能幫小明計算出最大的邊長是多少麼？

輸入格式

第一行包含兩個整數 N 和 K。

以下 N 行每行包含兩個整數 Hi 和 Wi。

輸入保證每位小朋友至少能獲得一塊 1×1 的巧克力。

# 整數二分法
# 判斷巧克力塊數夠不夠
def check(mid):
    count = 0
    for i in range(n):
        count += (lis[i][0]//mid) * (lis[i][1]//mid)
    if count >= k:
        return True
    
    

if __name__ == '__main__':
    n,k = map(int,input().strip().split())
    lis = [[int(i) for i in input().strip().split()]  for i in range(n)]
    l,r = 1,100000 # 答案區間 1≤Hi,Wi≤105
    while(l<r):
        mid = (l + r + 1) // 2
        if check(mid):l = mid # 巧克力塊數随增大而減小
        else:r = mid-1
    print(l)