14384 - 军粮均分
Time Limit : 1 秒
Memory Limit : 128 MB
某部将缴获的 N 块军粮分给 K 个连队，每块军粮为长方形（第 i 块尺寸为 Hi × Wi）。需从这些军粮中切出 K 块大小完全相同的正方形口粮（边长为整数），每位指战员一块。每块原料只能切不能拼接。请计算能切出的正方形口粮的最大边长。
Input
输入第一行为 N 和 K（1≤N,K≤10^5）， 接下来 N 行每行包含 Hi 和 Wi （1≤Hi,Wi≤10^5），且保证每位指战员至少能分得一块 1×1 的口粮
Output
输出能切出的正方形口粮的最大边长。
Examples
Input
2 10 6 5 5 6
Output
2