There are N events (numbered from 1 to N) and M contestants (numbered from 1 to M). For each event i, contestant j receives a predetermined number of points A_{i, j}.

A [subset] of these events will be selected, and the final score of contestant j, denoted s_{j}, will be the sum of their points for each event selected.

Formally, if S denotes the set of events chosen, then \displaystyle s_{j} = \sum_{x \in S} A_{x, j} for each 1 ≤ j ≤ M. If S is empty, we define s_{j} = 0 for each j.

The *differentiation* of the final scoreboard is equal to

\max_{i=1}^M (\sum_{j=1}^M |s_{j} - s_{i}|)

Find the maximum possible differentiation over all subsets of events. 

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of several lines.
- The first line of each test case contains two space-separated integers N and M — the number of events and contestants, respectively.
- The next N lines describe the events. The i-th of these N lines contains M space-separated integers A_{i, 1}, A_{i, 2}, \ldots, A_{i, M} — the j-th of which describes the number of points the j-th contestant earns for event i.

------ Output Format ------ 

For each test case, output on a new line the maximum differentiation over all subsets of events.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$0 ≤ A_{i, j} ≤ 10^{5}$
- The sum of $N\cdot M$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
3
1 1
1
3 3
1 0 1
1 2 1
1 2 1
4 2
1 3
5 1
6 8
2 1

----- Sample Output 1 ------ 
0
4
5
----- explanation 1 ------ 
Test case $1$: There are two possible subsets of events — either take the only event, or don't. In either case, the differentiation will be $0$.

Test case $2$: Take events $2$ and $3$ for a final scoreboard of $(2, 4, 2)$. The differentiation of this scoreboard is $4$, and it can be proven that this is the maximum.

Test case $3$: Take events $3$ and $5$, for a final scoreboard of $(7, 2)$, which has a differentiation of $5$.

Difficulty: VERY_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from sys import stdin, stdout
read = stdin.readline
t = int(read())
for testcase in range(t):
	(n, m) = map(int, read().split())
	scorearr = [list(map(int, read().split())) for i in range(n)]
	sumarr = [sum(i) for i in scorearr]
	cm = 0
	for i in range(m):
		cur = 0
		for j in range(n):
			temp = sumarr[j] - m * scorearr[j][i]
			if temp > 0:
				cur += temp
		if cur > cm:
			cm = cur
	for i in range(m):
		cur = 0
		for j in range(n):
			temp = m * scorearr[j][i] - sumarr[j]
			if temp > 0:
				cur += temp
		if cur > cm:
			cm = cur
	print(cm)


def DIFF_solu():
	max_ans = 0
	(n, m) = map(int, input().split())
	sum_i = []
	A = []
	for i in range(n):
		A.append(list(map(int, input().split())))
		sum_i.append(sum(A[-1]))
	for j in range(m):
		max_diff_1 = 0
		max_diff_2 = 0
		for i in range(n):
			diff = sum_i[i] - A[i][j] - A[i][j] * (m - 1)
			max_diff_1 += max(0, diff)
			max_diff_2 += max(0, -diff)
		max_ans = max(max_ans, max_diff_1, max_diff_2)
	return max_ans
t = int(input())
for _ in range(t):
	print(DIFF_solu())