该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

Dutchland 对 Russland 发起了突然入侵，Russland 反应不及，瞬间丢失了大片领土。

Russland 内务人民委员贝利亚受命组织敌后游击战。强哥作为工作团成员，主要负责协调物资的敌后供给工作。

题目描述

敌后游击队的常见任务之一就是炸掉 Dutchland 的铁路线，以切断后勤补给。这样的铁路线有 $K$ 条。

强哥的手中有 $N$ 块长方形的 TNT 炸药，其中第 $i$ 块是 $H_i \times W_i$ 的方格组成的长方形。

他现在需要把这些炸药分给游击队员们。每条铁路线都应当被分到一块 相同大小的正方形炸药。

强哥的数学很好，但是贝利亚每天大晚上都会带着他去 Kremlin 找慈父同志喝伏特加，所以他实在是没办法，把分配炸药的任务交给了你。

输入格式

第一行包含两个整数 $N$ 和 $K$。$(1 \le N,K \le 10^5)$。

以下 $N$ 行每行包含两个整数 $H_i$ 和 $W_i$。$(1 \le H_i,W_i \le 10^4)$。

输入保证每处铁路线都能被 TNT 炸。

输出格式

输出切出的炸药 最大的尺寸。分出去的每个炸药应当是 $x\times x$ 的方格组成的正方形，输出 $x$ 即可。

2 10  
6 5  
5 6

2