← 返回题目列表

Codeforces · 1808/B

B. 在赌场玩

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

全太阳系知名赌场Galaxy Luck推出了一款新的纸牌游戏。

在这个游戏中,有一副牌由 $$$n$$$ 卡组成。每张卡片上都写有 $$$m$$$ 数字。每个 $$$n$$$ 玩家都会从牌堆中收到一张牌。

然后所有玩家两人一组进行游戏,每对玩家只玩一次。因此,例如,如果总共有四名玩家,则进行六场比赛:第一场对第二场,第一场对第三场,第一场对第四场,第二场对第三场,第二场对第四场,第三场对第四场。

这些游戏都以某种方式决定胜负,但规则相当复杂,所以我们在这里不再描述。重要的是向获胜者支付多少筹码。让第一个玩家的牌上有数字 $$$a_1, a_2, \dots, a_m$$$,第二个玩家的牌上有数字 $$$b_1, b_2, \dots, b_m$$$。那么游戏的获胜者将获得$$$|a_1 - b_1| + |a_2 - b_2| + \dots + |a_m - b_m|$$$ 总底池筹码,其中 $$$|x|$$$ 表示 $$$x$$$ 的绝对值。

要确定总底池的大小,需要计算所有游戏获胜者的总奖金。由于一副牌中可能有很多牌和很多玩家,因此您被分配编写一个程序来执行所有必要的计算。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \cdot m \le 3\cdot 10^5$$$) - 这副牌中的牌数和单张牌上的数字数。

测试用例集中的以下 $$$n$$$ 行均包含 $$$m$$$ 整数 $$$c_{i,j}$$$ ($$$1 \le c_{i,j} \le 10^6$$$) - 第 $$$i$$$ 卡的描述。

保证所有测试中的总 $$$n \cdot m$$$ 不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个数字 — 所有游戏的奖金总额。

示例

输入 #1

3
3 5
1 4 2 8 5
7 9 2 1 4
3 8 5 3 1
1 4
4 15 1 10
4 3
1 2 3
3 2 1
1 2 1
4 2 7

输出 #1

50
0
31

注意

考虑第一个测试用例。

在第一名和第二名玩家之间的游戏中,获胜者获得 $$$|1-7| + |4-9| + |2-2| + |8-1| + |5-4| = 19$$$ 筹码。

在第一名和第三名玩家之间的游戏中,获胜者获得 $$$|1-3| + |4-8| + |2-5| + |8-3| + |5-1| = 18$$$ 筹码。

在第二名和第三名玩家之间的游戏中,获胜者获得 $$$|7-3| + |9-8| + |2-5| + |1-3| + |4-1| = 13$$$ 筹码。

筹码总数为 $$$19 + 18 + 13 = 50$$$ 筹码。