CF1825B LuoTianyi and the Table

洛天依给了你一个包含 $n \cdot m$ 个整数的数组 $b$。她要求你构造一个大小为 $n \times m$ 的表格 $a$，用这 $n \cdot m$ 个数填满，每个数必须且只能用一次。同时，她还要求你最大化如下的值： $$ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left(\max\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}-\min\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}\right) $$ 也就是说，我们考虑 $n \cdot m$ 个以 $(1,1)$ 为左上角、$(i,j)$ 为右下角的子表格（$1 \le i \le n$，$1 \le j \le m$），对于每个这样的子表格，计算其中最大元素与最小元素的差，然后将所有这些差值相加。你需要最大化最终的和。 请帮她求出最大可能的值，无需还原具体的表格。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 200$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 100$），表示表格的行数和列数。 每个测试用例的第二行包含 $n \cdot m$ 个整数 $b_1, b_2, \ldots, b_{n\cdot m}$（$-10^5 \le b_{i} \le 10^5$），表示你可以放入表格的数字。 注意，数组 $b$ 中的整数可能为负数。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示可以获得的最大值。

在第一个测试用例中，表格如下： 4 1 1 3 对于以 $(1,1)$ 为右下角的子表格，最大最小差为 $4-4=0$。 对于以 $(1,2)$ 为右下角的子表格，最大最小差为 $4-1=3$。 对于以 $(2,1)$ 为右下角的子表格，最大最小差为 $4-1=3$。 对于以 $(2,2)$ 为右下角的子表格，最大最小差为 $4-1=3$。 因此最大可能的值为 $0+3+3+3=9$。 在第二个测试用例中，所有元素都相等，所以所有差值都为 $0$，答案为 $0$。 由 ChatGPT 4.1 翻译