2238: 生日派对分巧克力
Description
小雨的生日派对，家中来了一群同学。妈妈买回 N 块长方形巧克力，想切成一样大的正方形分给大家。小雨希望每块正方形尽量大，显得大方；但巧克力不能拼接、也不能叠着凑，每个正方形只能从某一块巧克力上直接切出来。请你帮他算出这个最大的边长。
给定 N 块矩形巧克力，第 i 块长 h[i] 厘米、宽 w[i] 厘米。现在要把它们切成若干个边长为整数 x 厘米的正方形，要求：
· 每个正方形完整地取自同一块巧克力（不能拼接、不能折叠）；
· 所有正方形大小完全相同；
· 切出的正方形总数不少于 K。
求最大的 x。如果连 x = 1 都切不出 K 块，输出 0。
Input
输入格式
第一行两个整数 N K。接下来 N 行，每行两个整数 h[i] w[i]。
Output
输出格式
一行一个整数，表示最大的边长 x。
Sample Input Copy
2 10
6 5
5 6
Sample Output Copy
2
样例解释
样例 1：x = 2 时，6×5 与 5×6 两块分别能切出 3×2 = 6 块和 2×3 = 6 块，共 12 块，不少于 10；而 x = 3 时只有 2×1 + 1×2 = 4 块，不够，所以答案是 2。
HINT
1 ≤ N ≤ 10000，1 ≤ h[i], w[i] ≤ 100000，1 ≤ K ≤ 10⁹。
提示：想一想 x 变大时“能不能凑够 K 块”会怎样变化；也留意总块数可能非常大。
AI 辅助编程建议
①确认需求。 让 AI 用自己的话复述：正方形边长 x 必须是整数；每个正方形只能来自同一块巧克力，不能拼接；总数不少于 K 即可（不要求平均分）；无解时输出 0。再请它说明 x 与“能否凑够 K 块”之间的单调关系——这是能不能用二分的前提。
②生成程序。 指定考试要求的语言，请 AI 说明为什么可以二分、二分上下界怎么取（下界 1，上界取所有 h 与 w 的最大值），并给出一个判定函数。写完后追问一句关键问题：能不能用“所有巧克力总面积 ÷ x² ≥ K”来判断？请它解释为什么这样是错的（正方形不能拼接）。
③审查逻辑。 重点检查四处：判定函数必须是 Σ (h[i] // x) × (w[i] // x)，不能拿总面积去除；二分的循环边界与 mid 取法（上取整还是下取整）是否会造成死循环；当某块巧克力比 x 小时它贡献 0，不要写成负数；累加时数值可能达到 10¹⁴ 量级，C++ 中必须用 long long。
④补充测试。 除题面样例外，还应检查：x = 1 恰好够与恰好不够（验证无解输出 0）；所有巧克力都是 1×1；K = 1（应取最大的那条边）；存在很小的巧克力（贡献 0，不能取负）；答案恰好在二分上界；最大规模 N = 10000、边长 100000、K = 10⁹（同时测效率与溢出）。
⑤迭代修正。 如果实际输出与预期不一致，把输入、预期输出和实际输出一并提供给 AI，并说明怀疑方向（例如“是判定函数错还是二分边界错”）；修改后重新运行全部测试，不能只跑刚才失败的那一条。