CF1808B.Playing in a Casino
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Galaxy Luck, a well-known casino in the entire solar system, introduces a new card game.
In this game, there is a deck that consists of n cards. Each card has m numbers written on it. Each of the n players receives exactly one card from the deck.
Then all players play with each other in pairs, and each pair of players plays exactly once. Thus, if there are, for example, four players in total, then six games are played: the first against the second, the first against the third, the first against the fourth, the second against the third, the second against the fourth and the third against the fourth.
Each of these games determines the winner in some way, but the rules are quite complicated, so we will not describe them here. All that matters is how many chips are paid out to the winner. Let the first player's card have the numbers a1,a2,…,am , and the second player's card — b1,b2,…,bm . Then the winner of the game gets ∣a1−b1∣+∣a2−b2∣+⋯+∣am−bm∣ chips from the total pot, where ∣x∣ denotes the absolute value of x .
To determine the size of the total pot, it is necessary to calculate the winners' total winnings for all games. Since there can be many cards in a deck and many players, you have been assigned to write a program that does all the necessary calculations.
输入格式
Each test consists of several test cases. The first line contains one integer t ( 1≤t≤1000 ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers n and m ( 1≤n⋅m≤3⋅105 ) — the number of cards in the deck and the count of numbers on the one card.
Each of the following n lines of the test case set contains m integers ci,j ( 1≤ci,j≤106 ) — a description of the i -th card.
It is guaranteed that the total n⋅m in all tests does not exceed 3⋅105 .
输出格式
For each test case, print one number — the total amount of winnings from all games.
输入输出样例
输入#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
说明/提示
Consider the first test case.
In the game between the first and second player, the winner receives ∣1−7∣+∣4−9∣+∣2−2∣+∣8−1∣+∣5−4∣=19 chips.
In the game between the first and third player, the winner receives ∣1−3∣+∣4−8∣+∣2−5∣+∣8−3∣+∣5−1∣=18 in chips.
In the game between the second and third player, the winner receives ∣7−3∣+∣9−8∣+∣2−5∣+∣1−3∣+∣4−1∣=13 chips.
The total is 19+18+13=50 chips.