题目描述

小山和小西在玩一个矩阵游戏：
有一个 n × m 的矩阵，小山可以为每一行选择一个值作为该行的代表值。小西会从这些代表值中选择两个数作差（取绝对值）。
小山希望小西选出的差值尽可能小；小西希望自己选出的差值尽可能大。
请你计算，在两个人都采取最优策略的情况下，小西最终选出的两个代表值的差的绝对值是多少？

输入格式

从文件 matrix.in 中读入数据。
第一行两个整数 n, m。
接下来 n 行，每行 m 个整数。

输出格式

输出到文件 matrix.out 中。
一个整数，表示最终的差值。

3 3
1 2 9
4 5 6
7 8 3

2

样例解释 #1

两人都选择最优策略时，小山选择 {2, 4, 3} 作为三行的代表值。在此集合下，小西会选择差值最大的两个数 2 和 4，得到的最大差值为 |4 - 2| = 2。这是小山能够确保的最小最大差值。

数据范围

• 对于 10% 的数据，保证 m = 1。
• 对于另外 10% 的数据，保证 n = 2。
• 对于另外 20% 的数据，保证 2 ≤ n ≤ 8, 2 ≤ m ≤ 8。
• 对于另外 30% 的数据，保证 2 ≤ n ≤ 100, 2 ≤ m ≤ 100。
• 对于 100% 的数据，保证 2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000，矩阵中的整数绝对值不超过 10⁹。

题目来源

2025 山西省小学生编程未来星启航计划