← 返回题目列表

Codeforces · 1825/B

B. 洛天依和桌子

中文机器翻译题面 查看原题

LuoTianyi 给出了一个 $$$b$$$ 个 $$$n \cdot m$$$ 个整数的数组。她要求你构造一个大小为 $$$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}\右)$$$

这意味着我们考虑 $$$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$$$。

输出

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

示例

输入 #1

5
2 2
1 3 1 4
2 2
-1 -1 -1 -1
2 3
7 8 9 -3 10 8
3 2
4 8 -3 0 -7 1
4 3
-32030 59554 16854 -85927 68060 -64460 -79547 90932 85063 82703 -12001 38762

输出 #1

9
0
64
71
1933711

注意

第一个测试用例中,表格如下:

4113

在$$$(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$$$。