Timur's grandfather gifted him a chessboard to practice his chess skills. This chessboard is a grid $a$ with $n$ rows and $m$ columns with each cell having a non-negative integer written on it.

Timur's challenge is to place a bishop on the board such that the sum of all cells attacked by the bishop is maximal. The bishop attacks in all directions diagonally, and there is no limit to the distance which the bishop can attack. Note that the cell on which the bishop is placed is also considered attacked. Help him find the maximal sum he can get.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers $n$ and $m$ ($1 \le n \le 200$, $1 \leq m \leq 200$).

The following $n$ lines contain $m$ integers each, the $j$-th element of the $i$-th line $a_{ij}$ is the number written in the $j$-th cell of the $i$-th row $(0\leq a_{ij} \leq 10^6)$

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $4\cdot10^4$.


-----Output-----

For each test case output a single integer, the maximum sum over all possible placements of the bishop.


-----Examples-----

Input
4
4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
2 1
1
0
3 3
1 1 1
1 1 1
1 1 1
3 3
0 1 1
1 0 1
1 1 0
Output
20
1
5
3


-----Note-----

For the first test case here the best sum is achieved by the bishop being in this position:

Source: codeforces | Difficulty: EASY
Tags: Complete search

Implementation

Greedy algorithms


Solutions:
(I, R) = (lambda : map(int, input().split()), range)
for _ in R(*I()):
	(n, m) = I()
	a = [[*I()] for _ in R(n)]
	l = [0] * (m + n)
	r = l[:]
	for i in R(n):
		for j in R(m):
			b = a[i][j]
			l[i - j + m - 1] += b
			r[i + j] += b
	print(max((l[i - j + m - 1] + r[i + j] - a[i][j] for i in R(n) for j in R(m))))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	u = {d: sum((a[i][d - i] for i in range(n) if 0 <= d - i < m)) for d in range(n + m - 1)}
	v = {d: sum((a[i][d + i] for i in range(n) if 0 <= d + i < m)) for d in range(1 - n, m)}
	print(max((u[i + j] + v[j - i] - a[i][j] for i in range(n) for j in range(m))))


import sys
input = sys.stdin.readline

def init_diagonal_sum(n, m, arr):
	if n == 1 or m == 1:
		return
	add_sum = [0] * (n + m - 1)
	sub_sum = [0] * (n + m - 1)
	for i in range(n):
		for j in range(m):
			add_sum[i + j] += arr[i][j]
			sub_sum[i - j + (m - 1)] += arr[i][j]
	return (add_sum, sub_sum)

def get_max_score_bishop(n, m, arr):
	if n == 1 or m == 1:
		return
	(add_sum, sub_sum) = init_diagonal_sum(n, m, arr)
	max_score = 0
	for i in range(n):
		for j in range(m):
			max_score = max(max_score, add_sum[i + j] + sub_sum[i - j + (m - 1)] - arr[i][j])
	return max_score
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = [list(map(int, input().split())) for _ in range(n)]
	if n == 1:
		print(max(arr[0]))
	elif m == 1:
		print(max([num for inner_list in arr for num in inner_list]))
	else:
		print(get_max_score_bishop(n, m, arr))


(kvs, z) = (lambda : map(int, input().split()), range)
for _ in z(*kvs()):
	(n, m) = kvs()
	a = [[*kvs()] for _ in z(n)]
	l = [0] * (m + n)
	r = l[:]
	for i in z(n):
		for j in z(m):
			b = a[i][j]
			l[i - j + m - 1] += b
			r[i + j] += b
	print(max((l[i - j + m - 1] + r[i + j] - a[i][j] for i in z(n) for j in z(m))))


(k, o) = (lambda : map(int, input().split()), range)
for f in o(*k()):
	(n, m) = k()
	a = [[*k()] for t in o(n)]
	l = [0] * (m + n)
	r = l[:]
	for i in o(n):
		for j in o(m):
			b = a[i][j]
			l[i - j + m - 1] += b
			r[i + j] += b
	print(max((l[i - j + m - 1] + r[i + j] - a[i][j] for i in o(n) for j in o(m))))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	dL = [0] * (n + m + 2)
	dR = [0] * (n + m + 2)
	for i in range(n):
		for j in range(m):
			dL[i - j] += a[i][j]
			dR[i + j] += a[i][j]
	ans = 0
	for i in range(n):
		for j in range(m):
			ans = max(ans, dL[i - j] + dR[i + j] - a[i][j])
	print(ans)


from collections import defaultdict

def re(arr):
	mdia = defaultdict(int)
	adia = defaultdict(int)
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			mdia[j - i] += arr[i][j]
			adia[j + i] += arr[i][j]
	max_ = 0
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			if mdia[j - i] + adia[j + i] - arr[i][j] > max_:
				max_ = mdia[j - i] + adia[j + i] - arr[i][j]
	print(max_)
num = int(input())
for _ in range(num):
	(r, c) = list(map(int, input().split()))
	arr = [[0 * c] for _ in range(r)]
	for i in range(r):
		arr[i] = list(map(int, input().split()))
	re(arr)


from collections import defaultdict

def bishopAttack(m, n, board):
	majorDiagonal = defaultdict(int)
	minorDiagonal = defaultdict(int)
	for i in range(m):
		for j in range(n):
			majorDiagonal[i + j] += board[i][j]
			minorDiagonal[i - j] += board[i][j]
	maximum_damage = 0
	for i in range(m):
		for j in range(n):
			attack = majorDiagonal[i + j] + minorDiagonal[i - j] - board[i][j]
			maximum_damage = max(maximum_damage, attack)
	return maximum_damage
rep = int(input())
for _ in range(rep):
	(m, n) = map(int, input().split())
	board = []
	for _ in range(m):
		board.append(list(map(int, input().split())))
	print(bishopAttack(m, n, board))


t = int(input())

def maximum(row, col, arr):
	d1 = [0] * (row + col - 1)
	d2 = [0] * (row + col - 1)
	for i in range(row):
		for j in range(col):
			d1[j - i] += arr[i][j]
			d2[i + j] += arr[i][j]
	maxi = 0
	for i in range(row):
		for j in range(col):
			maxi = max(maxi, d1[j - i] + d2[i + j] - arr[i][j])
	print(maxi)
for i in range(t):
	grid = list(map(int, input().split(' ')))
	card = []
	for j in range(grid[0]):
		card.append(list(map(int, input().split(' '))))
	maximum(grid[0], grid[1], card)


def findMaxValue(grid, n, m):
	leftDiagonal = [0] * 440
	rightDiagonal = [0] * 440
	maxValue = float('-inf')
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			leftDiagonal[i + j] += grid[i][j]
			rightDiagonal[i - j + m] += grid[i][j]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			maxValue = max(maxValue, leftDiagonal[i + j] + rightDiagonal[i - j + m] - grid[i][j])
	return maxValue

def main():
	tc = int(input())
	for _ in range(tc):
		(n, m) = map(int, input().split())
		grid = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for __ in range(n):
			l = list(map(int, input().split()))
			for j in range(m):
				grid[__ + 1][j + 1] = l[j]
		print(findMaxValue(grid, n, m))
main()


def calc(n, m, field):
	(bslash, slash) = ({}, {})
	for i in range(n):
		for j in range(m):
			bslash[i - j] = bslash.get(i - j, 0) + field[i][j]
			slash[i + j] = slash.get(i + j, 0) + field[i][j]
	return (bslash, slash)

def xsum(field, x, y, bslash, slash):
	return bslash[x - y] + slash[x + y] - field[x][y]

def main():
	(n, m) = map(int, input().split())
	field = [[int(x) for x in input().split()] for _ in range(n)]
	(bslash, slash) = calc(n, m, field)
	result = -1
	for i in range(n):
		for j in range(m):
			result = max(result, xsum(field, i, j, bslash, slash))
	print(result)
t = int(input())
for _ in range(t):
	main()


import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	a = [None] * n
	d1 = [0] * (n + m)
	d2 = [0] * (n + m)
	for i in range(n):
		a[i] = list(map(int, inp().split()))
		for j in range(m):
			d1[i + j] += a[i][j]
			d2[i - j] += a[i][j]
	res = 0
	for i in range(n):
		for j in range(m):
			cost = 0
			res = max(res, d1[i + j] + d2[i - j] - a[i][j])
	print(res)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


q = int(input())
for test in range(q):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	sm1 = [0] * (n + m)
	sm2 = [0] * (n + m)
	for i in range(n):
		for j in range(m):
			sm1[i + j] += a[i][j]
			sm2[i - j + m] += a[i][j]
	ans = 0
	for i in range(n):
		for j in range(m):
			ans = max(ans, sm1[i + j] + sm2[i - j + m] - a[i][j])
	print(ans)


def task(n, m, a):
	lefts = dict()
	rights = dict()
	for i in range(n):
		for j in range(m):
			leftkey = i - j
			if not leftkey in lefts:
				lefts[leftkey] = 0
			lefts[leftkey] += a[i][j]
			rightkey = i + j
			if not rightkey in rights:
				rights[rightkey] = 0
			rights[rightkey] += a[i][j]
	best = 0
	for i in range(n):
		for j in range(m):
			leftkey = i - j
			rightkey = i + j
			suma = lefts[leftkey] + rights[rightkey] - a[i][j]
			best = max(best, suma)
	print(best)
t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		b = list(map(int, input().split()))
		a.append(b)
	task(n, m, a)


import sys

def input():
	return sys.stdin.readline().rstrip()

def main():

	def add_rightdown(r: int, c: int):
		cur_sum = 0
		visited = []
		while r < n and c < m:
			cur_sum += board[r][c]
			visited.append((r, c))
			r += 1
			c += 1
		for (r, c) in visited:
			score[r][c] += cur_sum

	def add_leftdown(r: int, c: int):
		cur_sum = 0
		visited = []
		while r < n and 0 <= c:
			cur_sum += board[r][c]
			visited.append((r, c))
			r += 1
			c -= 1
		for (r, c) in visited:
			score[r][c] += cur_sum
	t = int(input())
	for tc in range(t):
		(n, m) = map(int, input().split())
		board = [list(map(int, input().split())) for _ in range(n)]
		score = [[0 for col in range(m)] for row in range(n)]
		for col in range(m):
			add_rightdown(0, col)
		for row in range(1, n):
			add_rightdown(row, 0)
		for col in range(m):
			add_leftdown(0, col)
		for row in range(1, n):
			add_leftdown(row, m - 1)
		max_sum = 0
		for row in range(n):
			for col in range(m):
				max_sum = max(max_sum, score[row][col] - board[row][col])
		print(max_sum)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict as dd

def solve():
	res = 0
	(N, M) = map(int, input().split())
	A = [list(map(int, input().split())) for _ in range(N)]
	RU = dd(int)
	RD = dd(int)
	for i in range(N):
		for j in range(M):
			RU[i + j] += A[i][j]
			RD[i - j] += A[i][j]
	for i in range(N):
		for j in range(M):
			res = max(res, RU[i + j] + RD[i - j] - A[i][j])
	print(res)
	return
T = int(input())
for _ in range(T):
	solve()


from collections import defaultdict

def fun(a, n, m):
	sf = defaultdict(int)
	df = defaultdict(int)
	for i in range(n):
		for j in range(m):
			sf[i + j] += a[i][j]
			df[i - j] += a[i][j]
	mx = 0
	for i in range(n):
		for j in range(m):
			th = sf[i + j] + df[i - j] - a[i][j]
			mx = max(mx, th)
	return mx
tc = int(input())
for _ in range(1, tc + 1):
	(n, m) = list(map(int, input().split()))
	a = []
	for i in range(n):
		l = list(map(int, input().split()))
		a.append(l)
	print(fun(a, n, m))


t = int(input())
for j in range(t):
	(n, m) = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	x = [0 for i in range(n + m - 1)]
	y = [0 for i in range(n + m - 1)]
	for i in range(n):
		for j in range(m):
			x[i + j] += a[i][j]
	for i in range(n):
		for j in range(m):
			y[i + j] += a[i][m - 1 - j]
	mn = 0
	for i in range(n):
		for j in range(m):
			mn = max(x[i + j] + y[m - 1 - j + i] - a[i][j], mn)
	print(mn)


def diagonals(L):
	(h, w) = (len(L), len(L[0]))
	return [[L[h - p + q - 1][q] for q in range(max(p - h + 1, 0), min(p + 1, w))] for p in range(h + w - 1)]

def antidiagonals(L):
	(h, w) = (len(L), len(L[0]))
	return [[L[p - q][q] for q in range(max(p - h + 1, 0), min(p + 1, w))] for p in range(h + w - 1)]
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	mygrid = []
	for i in range(n):
		gridrow = list(map(int, input().strip().split()))
		mygrid.append(gridrow)
	Dg = diagonals(mygrid)
	Ag = antidiagonals(mygrid)
	Dattack = [sum(x) for x in diagonals(mygrid)]
	Aattack = [sum(x) for x in antidiagonals(mygrid)]
	power = 0
	current_power = 0
	for i in range(n):
		for j in range(m):
			current_power = Aattack[i + j] + Dattack[n - 1 - i + j] - mygrid[i][j]
			if current_power > power:
				power = current_power
	print(power)


t = int(input())
for nabor in range(t):
	(n, m) = map(int, input().split())
	arr = tuple((tuple(map(int, input().split())) for y in range(n)))
	sums = [0] * (n + m - 1)
	sums2 = [0] * (n + m - 1)
	for y in range(n):
		nn = n - y - 1
		for (x, i) in enumerate(arr[y]):
			sums[x + y] += i
			sums2[x + nn] += i
	Max = 0
	for y in range(n):
		nn = n - y - 1
		for (x, i) in enumerate(arr[y]):
			Max = max(Max, sums[x + y] + sums2[x + nn] - arr[y][x])
	print(Max)


def solve(grid):
	(m, n) = (len(grid), len(grid[0]))
	b1 = {}
	for i in range(n):
		b1[-i] = sum([grid[k][i + k] for k in range(min(m, n - i))])
	for i in range(1, m):
		b1[i] = sum([grid[i + k][k] for k in range(min(m - i, n))])
	b2 = {}
	for i in range(n):
		b2[i] = sum([grid[k][i - k] for k in range(min(m, i + 1))])
	for i in range(1, m):
		b2[i + n - 1] = sum([grid[i + k][n - 1 - k] for k in range(min(m - i, n))])
	ans = 0
	for i in range(m):
		for j in range(n):
			tmp = b1[i - j] + b2[i + j] - grid[i][j]
			ans = max(ans, tmp)
	return ans
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	grid = []
	for i in range(N):
		grid.append(list(map(int, input().split())))
	ans = solve(grid)
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	s = []
	a = []
	b = []
	for i in range(n):
		s += [list(map(int, input().split()))]
	for j in range(m):
		(sm1, sm2) = (0, 0)
		for i in range(min(j + 1, n)):
			sm1 += s[i][j - i]
		for i in range(min(n, m - j)):
			sm2 += s[i][j + i]
		a += [sm1]
		b += [sm2]
	for i in range(1, n):
		(sm1, sm2) = (0, 0)
		for j in range(m - 1, -1 + m - min(m, n - i), -1):
			sm1 += s[i - j + m - 1][j]
		for j in range(min(n - i, m)):
			sm2 += s[i + j][j]
		a += [sm1]
		b = [sm2] + b
	mx = 0
	for i in range(n):
		for j in range(m):
			mx = max(mx, a[i + j] + b[j + n - i - 1] - s[i][j])
	print(mx)


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	g = [0] * (n + m - 1)
	p = [0] * (n + m - 1)
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
		for j in range(m):
			p[i + j] += a[i][j]
			try:
				g[m - j + i - 1] += a[i][j]
			except:
				print('m,j,i =', m, j, i)
	h_max = 0
	for i in range(n):
		for j in range(m):
			h = g[m - j - 1 + i] + p[j + i] - a[i][j]
			if h > h_max:
				h_max = h
	print(h_max)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	d1 = [0] * (n + m - 1)
	d2 = [0] * (n + m - 1)
	for i in range(n):
		for j in range(m):
			d1[i + j] += arr[i][j]
			d2[i - j + m - 1] += arr[i][j]
	maxx = 0
	for i in range(n):
		for j in range(m):
			maxx = max(maxx, d1[i + j] + d2[i - j + m - 1] - arr[i][j])
	print(maxx)


import sys
input = sys.stdin.readline
mp = [0] * 200

def solve():
	(n, m) = map(int, input().split())
	ans = 0
	a1 = [0] * (n + m + 2)
	a2 = [0] * (n + m + 2)
	ans = 0
	for i in range(n):
		mp[i] = list(map(int, input().split()))
		for j in range(m):
			a1[i + j] += mp[i][j]
			a2[i - j] += mp[i][j]
	for i in range(n):
		for j in range(m):
			ans = max(ans, a1[i + j] + a2[i - j] - mp[i][j])
	print(ans)
for _ in range(int(input())):
	solve()


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[*map(int, input().split())] for i in range(n)]
	kd = m + n - 1
	gd = [0] * kd
	pd = [0] * kd
	for i in range(n):
		for j in range(m):
			gd[i - j] += a[i][j]
			pd[i + j] += a[i][j]
	for i in range(n):
		for j in range(m):
			a[i][j] = gd[i - j] + pd[i + j] - a[i][j]
	print(max(map(max, a)))


import sys
from collections import defaultdict
input = sys.stdin.readline
import heapq

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
testcase = inp()
for i in range(0, testcase):
	(n, m) = inlt()
	grid = []
	for i in range(n):
		grid.append(inlt())
	d1 = defaultdict(int)
	d2 = defaultdict(int)
	for i in range(n):
		for j in range(m):
			d1[i - j] += grid[i][j]
			d2[i + j] += grid[i][j]
	Max = 0
	for i in range(n):
		for j in range(m):
			Max = max(Max, d1[i - j] + d2[i + j] - grid[i][j])
	print(Max)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	lst = []
	for i in range(n):
		lst.append(list(map(int, input().split())))
	dic1 = {}
	dic2 = {}
	for i in range(n):
		for j in range(m):
			if i + j in dic1:
				dic1[i + j] += lst[i][j]
			else:
				dic1[i + j] = lst[i][j]
			if i - j in dic2:
				dic2[i - j] += lst[i][j]
			else:
				dic2[i - j] = lst[i][j]
	sumlist = []
	for i in range(n):
		for j in range(m):
			sumlist.append(dic1[i + j] + dic2[i - j] - lst[i][j])
	print(max(sumlist))


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, m) = [int(d) for d in input().split()]
	current = []
	for _ in range(n):
		current.append([int(k) for k in input().split()])
	frw_diagonal_sum = defaultdict(int)
	bkw_diagonal_sum = defaultdict(int)
	for i in range(n):
		for j in range(m):
			frw_diagonal_sum[i + j] += current[i][j]
			bkw_diagonal_sum[i - j] += current[i][j]
	an = float('-inf')
	for i in range(n):
		for j in range(m):
			an = max(an, frw_diagonal_sum[i + j] + bkw_diagonal_sum[i - j] - current[i][j])
	print(an)


from collections import defaultdict
p = int(input())
for _ in range(p):
	[n, m] = list(map(int, input().split(' ')))
	ls = []
	for i in range(n):
		ls.append(list(map(int, input().split(' '))))
	d_up = defaultdict(int)
	d_down = defaultdict(int)
	for i in range(n):
		for j in range(m):
			d_up[i + j] += ls[i][j]
			d_down[i - j] += ls[i][j]
	mx_d = float('-inf')
	for i in range(n):
		for j in range(m):
			mx_d = max(mx_d, d_up[i + j] + d_down[i - j] - ls[i][j])
	print(mx_d)


from collections import defaultdict

def solve(grid):
	(slant1, slant2) = (defaultdict(int), defaultdict(int))
	(M, N) = (len(grid), len(grid[0]))
	for i in range(M):
		for j in range(N):
			slant1[i + j] += grid[i][j]
			slant2[i - j] += grid[i][j]
	max_val = -1
	for i in range(M):
		for j in range(N):
			current_sum = slant1[i + j] + slant2[i - j] - grid[i][j]
			max_val = max(max_val, current_sum)
	return max_val
tests = int(input())
for _ in range(tests):
	(r, c) = list(map(int, input().split()))
	grid = []
	for i in range(r):
		grid.append(list(map(int, input().split())))
	print(solve(grid))


def solution(matrix):
	positive = {}
	negative = {}
	res = 0
	for i in range(len(matrix)):
		for j in range(len(matrix[i])):
			positive[i + j] = matrix[i][j] + positive.get(i + j, 0)
			negative[i - j] = matrix[i][j] + negative.get(i - j, 0)
	for i in range(len(matrix)):
		for j in range(len(matrix[i])):
			if i + j in positive and i - j in negative:
				res = max(res, positive[i + j] + negative[i - j] - matrix[i][j])
	return res
q1 = int(input())
for i in range(q1):
	q2 = list(map(int, input().split()))
	mat = []
	for j in range(q2[0]):
		mat.append(list(map(int, input().split())))
	print(solution(mat))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	a = []
	arr = [0] * (n + m - 1)
	brr = [0] * (n + m - 1)
	for i in range(n):
		a.append(list(map(int, input().split(' '))))
		for j in range(m):
			arr[i + j] += a[i][j]
			brr[m - j + i - 1] += a[i][j]
		max_value = 0
		value = 0
	for i in range(n):
		for j in range(m):
			value = arr[i + j] + brr[m - j + i - 1] - a[i][j]
			if value > max_value:
				max_value = value
	print(max_value)


for i in range(int(input())):
	(n, m) = [int(a) for a in input().split()]
	lst = []
	dr = [0] * (n + m + 5)
	dl = [0] * (n + m + 5)
	for i in range(n):
		lst.append([int(a) for a in input().split()])
		for j in range(m):
			dr[i + j] += lst[i][j]
			dl[i - j] += lst[i][j]
	ans = 0
	for i in range(n):
		for j in range(m):
			ans = max(ans, dr[i + j] + dl[i - j] - lst[i][j])
	print(ans)


import collections

def method(graph):
	(m, n) = (len(graph), len(graph[0]))
	rec1 = collections.defaultdict(int)
	rec2 = collections.defaultdict(int)
	for i in range(m):
		for j in range(n):
			rec1[i + j] += graph[i][j]
			rec2[i - j] += graph[i][j]
	ans = 0
	for i in range(m):
		for j in range(n):
			ans = max(ans, rec1[i + j] + rec2[i - j] - graph[i][j])
	return ans
t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().split())))
	print(method(graph))


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = (int(x) for x in input().split())
	grid = []
	for _ in range(n):
		grid.append([int(x) for x in input().split()])
	(d, u) = (defaultdict(int), defaultdict(int))
	for r in range(n):
		for c in range(m):
			d[r - c] += grid[r][c]
			u[r + c] += grid[r][c]
	ans = 0
	for r in range(n):
		for c in range(m):
			ans = max(ans, d[r - c] + u[r + c] - grid[r][c])
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	board = [list(map(int, input().split())) for _ in range(n)]
	d_plus = {i: 0 for i in range(m + n)}
	d_minus = {i: 0 for i in range(-m - n, m + n)}
	for i in range(n):
		for j in range(m):
			d_plus[i + j] += board[i][j]
			d_minus[i - j] += board[i][j]
	ans = 0
	for i in range(n):
		for j in range(m):
			ans = max(ans, d_plus[i + j] + d_minus[i - j] - board[i][j])
	print(ans)


from collections import defaultdict
t = int(input())

def solve():
	(n, m) = map(int, input().split())
	board = [list(map(int, input().split())) for _ in range(n)]
	rightdown = defaultdict(int)
	rightup = defaultdict(int)
	for i in range(n):
		for j in range(m):
			rightdown[i + j] += board[i][j]
			rightup[i - j] += board[i][j]
	out = 0
	for i in range(n):
		for j in range(m):
			out = max(out, rightdown[i + j] + rightup[i - j] - board[i][j])
	print(out)
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	board = []
	(n, m) = map(int, input().split())
	for _ in range(n):
		row = list(map(int, input().split()))
		board.append(row)
	l = [0] * (m + n)
	r = [0] * (m + n)
	for i in range(n):
		for j in range(m):
			b = board[i][j]
			l[i - j + m - 1] += b
			r[i + j] += b
	print(max((l[i - j + m - 1] + r[i + j] - board[i][j] for i in range(n) for j in range(m))))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	board = []
	for i in range(n):
		board.append(list(map(int, input().split())))
	up_mht = {}
	down_mht = {}
	for i in range(0, m + n - 1):
		up_mht[i] = 0
		down_mht[i] = 0
	for i in range(n):
		for j in range(m):
			up_mht[i + j] += board[i][j]
	for i in range(n):
		for j in range(m):
			down_mht[n - 1 - i + j] += board[i][j]
	ans = []
	for i in range(n):
		for j in range(m):
			cand = up_mht[i + j] + down_mht[n - 1 - i + j] - board[i][j]
			ans.append(cand)
	print(max(ans))


import math

def dig(brd, d1, d2):
	for i in range(len(brd)):
		for j in range(len(brd[0])):
			if i - j in d1:
				d1[i - j] += brd[i][j]
			else:
				d1[i - j] = brd[i][j]
			if i + j in d2:
				d2[i + j] += brd[i][j]
			else:
				d2[i + j] = brd[i][j]

def fun(brd):
	ans = [[0 for i in range(len(brd[0]))] for _ in range(len(brd))]
	m = 0
	pdig = {}
	ndig = {}
	dig(brd, pdig, ndig)
	m = 0
	for i in range(len(brd)):
		for j in range(len(brd[0])):
			val = pdig[i - j] + ndig[i + j] - brd[i][j]
			if val > m:
				m = val
	return [m]
n = int(input())
for _ in range(n):
	q = input().split()
	board = []
	for m in range(int(q[0])):
		arr = input().split()
		arr = list(map(int, arr))
		board.append(arr)
	x = fun(board)
	for i in x:
		print(i, end=' ')
	print()


import collections
import sys
input = sys.stdin.readline

def input_single_integer():
	return int(input())

def input_list():
	return list(map(int, input().split()))

def input_string():
	s = input()
	return list(s[:len(s) - 1])

def input_space_seperated_integer_variables():
	return map(int, input().split())

def find_x_sum(chessboard, n, m):
	x = collections.defaultdict(int)
	y = collections.defaultdict(int)
	for i in range(n):
		for j in range(m):
			x[i + j] += chessboard[i][j]
			y[i - j] += chessboard[i][j]
	max_so_far = 0
	for i in range(n):
		for j in range(m):
			max_so_far = max(max_so_far, x[i + j] + y[i - j] - chessboard[i][j])
	print(max_so_far)
test_case = input_single_integer()
while test_case:
	(m, n) = input_space_seperated_integer_variables()
	chessboard = []
	for i in range(m):
		row = input_list()
		chessboard.append(row)
	find_x_sum(chessboard, m, n)
	test_case -= 1


from collections import defaultdict
for i in range(int(input())):
	z = []
	(x, y) = map(int, input().split())
	for j in range(x):
		z.append([int(k) for k in input().split()])
	d = defaultdict(int)
	e = defaultdict(int)
	for l in range(x):
		for m in range(y):
			d[l - m] += z[l][m]
			e[l + m] += z[l][m]
	ma = 0
	for l in range(x):
		for m in range(y):
			ma = max(ma, d[l - m] + e[l + m] - z[l][m])
	print(ma)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	(d1, d2) = ([0] * (n + m - 1), [0] * (n + m - 1))
	for i in range(n):
		for j in range(m):
			d1[i + j] += a[i][j]
			d2[i - j] += a[i][j]
	for i in range(n):
		for j in range(m):
			a[i][j] = d1[i + j] + d2[i - j] - a[i][j]
	print(max(map(max, a)))


for pratyush in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		l = list(map(int, input().split()))
		a.append(l)
	c = m + n - 1
	(p, s) = ([0] * c, [0] * c)
	for i in range(n):
		for j in range(m):
			p[i - j] += a[i][j]
			s[i + j] += a[i][j]
	h = 0
	for i in range(n):
		for j in range(m):
			a[i][j] = p[i - j] + s[i + j] - a[i][j]
			if h < a[i][j]:
				h = a[i][j]
	print(h)


z = lambda : map(int, input().split())
(t,) = z()
for _ in [1] * t:
	(n, m) = z()
	ch = []
	p = [0] * (n + m - 1)
	q = [0] * (n + m - 1)
	for i in [1] * n:
		ch.append([*z()])
	for i in range(n):
		for j in range(m):
			p[i - j] += ch[i][j]
			q[i + j] += ch[i][j]
	mx = -2000000000.0
	for i in range(n):
		for j in range(m):
			mx = max(mx, p[i - j] + q[i + j] - ch[i][j])
	print(mx)


for k in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	l = []
	for i in range(n):
		l.append([int(j) for j in input().split()])
	(l1, l2) = ([0] * (n + m - 1), [0] * (n + m - 1))
	for i in range(n):
		for j in range(m):
			l1[i + j] += l[i][j]
			l2[j - i + n - 1] += l[i][j]
	ans = 0
	for i in range(n):
		for j in range(m):
			ans = max(ans, l1[i + j] + l2[j - i + n - 1] - l[i][j])
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dr = [0] * (m + n)
	dl = [0] * (m + n)
	row = []
	ans = 0
	for i in range(n):
		row.append(list(map(int, input().split())))
		for j in range(m):
			dr[i + j] += row[i][j]
			dl[i - j + m] += row[i][j]
	for i in range(n):
		for j in range(m):
			ans = max(ans, dr[i + j] + dl[i - j + m] - row[i][j])
	print(ans)


def xsum(x) -> int:
	forward = {}
	backward = {}
	maximum = 0
	for row in range(len(x)):
		for col in range(len(x[0])):
			forward[row + col] = x[row][col] + forward.get(row + col, 0)
			backward[row - col] = x[row][col] + backward.get(row - col, 0)
	for row in range(len(x)):
		for col in range(len(x[0])):
			maximum = max(maximum, forward[row + col] + backward[row - col] - x[row][col])
	return maximum
size = int(input())
for _ in range(size):
	(row, col) = map(int, input().split())
	Lists = []
	for _ in range(row):
		Lists.append(list(map(int, input().split())))
	result = xsum(Lists)
	print(result)


from collections import defaultdict

def helper(grid):
	(row, col) = (len(grid), len(grid[0]))
	diagonal1 = defaultdict(int)
	diagonal2 = defaultdict(int)
	for r in range(row):
		for c in range(col):
			diagonal1[r - c] += grid[r][c]
			diagonal2[r + c] += grid[r][c]
	max_sum = float('-inf')
	for r in range(row):
		for c in range(col):
			cur = diagonal1[r - c] + diagonal2[r + c] - grid[r][c]
			max_sum = max(max_sum, cur)
	return max_sum
length = int(input())
for _ in range(length):
	size = list(map(int, input().split()))
	grid = []
	for i in range(size[0]):
		row = list(map(int, input().split()))
		grid.append(row)
	print(helper(grid))


for test in range(int(input())):
	diag = {}
	anti = {}
	matrix = []
	for x in range(list(map(int, input().split()))[0]):
		matrix.append(list(map(int, input().split())))
	maxx = 0
	for row in range(len(matrix)):
		for col in range(len(matrix[row])):
			dg = row + col
			ati = col - row
			diag[dg] = diag.get(dg, 0) + matrix[row][col]
			anti[ati] = anti.get(ati, 0) + matrix[row][col]
	maxx = 0
	for row in range(len(matrix)):
		for col in range(len(matrix[row])):
			dg = col + row
			at = col - row
			maxx = max(diag[dg] + anti[at] - matrix[row][col], maxx)
	print(maxx)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	matrix = [list(map(int, input().split())) for i in range(n)]
	diagonalSum1 = defaultdict(int)
	diagonalSum2 = defaultdict(int)
	for row in range(len(matrix)):
		for col in range(len(matrix[0])):
			diagonalSum1[col - row] += matrix[row][col]
			diagonalSum2[col + row] += matrix[row][col]
	maximumSum = 0
	for row in range(len(matrix)):
		for col in range(len(matrix[0])):
			firstDiagonalSum = diagonalSum1[col - row]
			secondDiagonalSum = diagonalSum2[col + row]
			cellSum = firstDiagonalSum + secondDiagonalSum - matrix[row][col]
			if cellSum > maximumSum:
				maximumSum = cellSum
	print(maximumSum)


from collections import defaultdict
testCases = int(input())
for _ in range(testCases):
	rightDiagonal = defaultdict(int)
	leftDiagonal = defaultdict(int)
	chessboard = []
	(rows, columns) = list(map(int, input().split()))
	for index in range(rows):
		row = list(map(int, input().split()))
		chessboard.append(row)
		length = len(row)
		for i in range(length):
			rightDiagonal[index - i] += row[i]
			leftDiagonal[index + i] += row[i]
	maxSum = -1
	for i in range(rows):
		for j in range(columns):
			sum = rightDiagonal[i - j] + leftDiagonal[i + j] - chessboard[i][j]
			maxSum = max(maxSum, sum)
	print(maxSum)


from collections import defaultdict
testCases = int(input())
for _ in range(testCases):
	rd = defaultdict(int)
	ld = defaultdict(int)
	chessboard = []
	(rows, columns) = list(map(int, input().split()))
	for index in range(rows):
		row = list(map(int, input().split()))
		chessboard.append(row)
		length = len(row)
		for i in range(length):
			rd[index - i] += row[i]
			ld[index + i] += row[i]
	maxi = -1
	for i in range(rows):
		for j in range(columns):
			sum = rd[i - j] + ld[i + j] - chessboard[i][j]
			maxi = max(maxi, sum)
	print(maxi)


from collections import *
test_case = int(input())
for _ in range(test_case):
	(n, m) = map(int, input().split())
	dctMD = defaultdict(int)
	dctOD = defaultdict(int)
	mtr = []
	for _ in range(n):
		row = list(map(int, input().split()))
		mtr.append(row)
	for i in range(n):
		for j in range(m):
			dctMD[i - j] += mtr[i][j]
			dctOD[i + j] += mtr[i][j]
	res = 0
	for i in range(n):
		for j in range(m):
			res = max(res, dctMD[i - j] + dctOD[i + j] - mtr[i][j])
	print(res)


from collections import defaultdict
size_of_test_case = int(input())
for _ in range(size_of_test_case):
	(rows, cols) = map(int, input().split())
	grid = []
	for _ in range(rows):
		row_val = list(map(int, input().split()))
		grid.append(row_val)
	difference_of_row_col = defaultdict(int)
	sum_of_row_col = defaultdict(int)
	max_val = float('-inf')
	length_grid = len(grid)
	for (row, row_val) in enumerate(grid):
		for col in range(len(row_val)):
			sum_of_row_col[col + row] += row_val[col]
			difference_of_row_col[row - col] += row_val[col]
	for (row, row_val) in enumerate(grid):
		for col in range(len(row_val)):
			score = sum_of_row_col[col + row] + difference_of_row_col[row - col] - row_val[col]
			max_val = max(score, max_val)
	print(max_val)


n = int(input())
for i in range(n):
	(r, m) = list(map(int, input().split()))
	mat = []
	for i in range(r):
		mat.append(list(map(int, input().split())))
	from collections import defaultdict
	row = len(mat)
	col = len(mat[0])
	diagonal = defaultdict(int)
	anti_diagonal = defaultdict(int)
	for i in range(row):
		for j in range(col):
			diagonal[i + j] += mat[i][j]
			anti_diagonal[j - i] += mat[i][j]
	_max = 0
	for i in range(row):
		for j in range(col):
			if diagonal[i + j] + anti_diagonal[j - i] - mat[i][j] > _max:
				_max = diagonal[i + j] + anti_diagonal[j - i] - mat[i][j]
	print(_max)


from collections import defaultdict
testCases = int(input())
for _ in range(testCases):
	nm = input().split()
	rows = int(nm[0])
	cols = int(nm[1])
	diagSum1 = defaultdict(int)
	diagSum2 = defaultdict(int)
	grid = []
	for _ in range(rows):
		row = list(map(int, input().split()))
		grid.append(row)
	for row in range(rows):
		for col in range(cols):
			num = grid[row][col]
			diagSum1[row - col] += num
			diagSum2[row + col] += num
	maxx = 0
	for row in range(rows):
		for col in range(cols):
			num = grid[row][col]
			summ = diagSum1[row - col] + diagSum2[row + col] - num
			maxx = max(maxx, summ)
	print(maxx)


def bishopAttack(matrix):
	m = len(matrix)
	n = len(matrix[0])
	forward = {}
	backward = {}
	for row in range(m):
		for col in range(n):
			if row - col in forward:
				forward[row - col] += matrix[row][col]
			else:
				forward[row - col] = matrix[row][col]
			if row + col in backward:
				backward[row + col] += matrix[row][col]
			else:
				backward[row + col] = matrix[row][col]
	maxx = 0
	for row in range(m):
		for col in range(n):
			curSum = forward[row - col] + backward[row + col] - matrix[row][col]
			maxx = max(maxx, curSum)
	return maxx
tests = int(input())
for i in range(tests):
	inp = input().split(' ')
	(n, m) = (int(inp[0]), int(inp[1]))
	matrix = []
	for j in range(n):
		row = list(map(int, input().split(' ')))
		matrix.append(row)
	print(bishopAttack(matrix))


import collections

def process(matrix, rows, cols):
	diff = collections.defaultdict(int)
	add = collections.defaultdict(int)
	for row in range(rows):
		for col in range(cols):
			diff[row - col] += matrix[row][col]
			add[row + col] += matrix[row][col]
	maximal_res = 0
	for row in range(rows):
		for col in range(cols):
			maximal_res = max(maximal_res, diff[row - col] + add[row + col] - matrix[row][col])
	print(maximal_res)
test = int(input())
for i in range(test):
	(rows, cols) = list(map(int, input().split()))
	mat = []
	for j in range(rows):
		temp = list(map(int, input().split()))
		mat.append(temp)
	process(mat, rows, cols)


from collections import defaultdict
test_num = int(input())
for _ in range(test_num):
	input_ = []
	(rows, cols) = list(map(int, input().split(' ')))
	max_ = 0
	for _ in range(rows):
		cell = list(map(int, input().split()))
		input_.append(cell)
	sum_hash_map = defaultdict(int)
	diff_hash_map = defaultdict(int)
	res = []
	for row in range(rows):
		for col in range(cols):
			diff_hash_map[col - row] += input_[row][col]
			sum_hash_map[col + row] += input_[row][col]
	for row in range(rows):
		for col in range(cols):
			sum_ = diff_hash_map[col - row] + sum_hash_map[col + row] - input_[row][col]
			max_ = max(max_, sum_)
	print(max_)


from collections import defaultdict
for _ in range(int(input())):
	(row, col) = list(map(int, input().split()))
	board = []
	for temp in range(row):
		l = list(map(int, input().split()))
		board.append(l)
	diagonal = defaultdict(int)
	diagonal2 = defaultdict(int)
	for i in range(len(board)):
		for j in range(len(board[i])):
			diagonal[j - i] += board[i][j]
			diagonal2[j + i] += board[i][j]
	maxSum = float('-inf')
	for i in range(len(board)):
		for j in range(len(board[i])):
			curSum = diagonal[j - i] + diagonal2[j + i] - board[i][j]
			maxSum = max(maxSum, curSum)
	print(maxSum)


import sys
from collections import defaultdict
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		(row, col) = list(map(int, input().split()))
		grid = []
		for i in range(row):
			nums = list(map(int, input().split()))
			grid.append(nums)
		diagonal_1_sum_map = defaultdict(int)
		diagonal_2_sum_map = defaultdict(int)
		for i in range(row):
			for j in range(col):
				diagonal_1_key = i + j
				diagonal_2_key = i - j
				diagonal_1_sum_map[diagonal_1_key] += grid[i][j]
				diagonal_2_sum_map[diagonal_2_key] += grid[i][j]
		max_cross_sum = 0
		for i in range(row):
			for j in range(col):
				diagonal_1_key = i + j
				diagonal_2_key = i - j
				diagonal_1_sum = diagonal_1_sum_map[diagonal_1_key]
				diagonal_2_sum = diagonal_2_sum_map[diagonal_2_key]
				total_digonal_sum = diagonal_1_sum + diagonal_2_sum - grid[i][j]
				max_cross_sum = max(max_cross_sum, total_digonal_sum)
		print(max_cross_sum)
main()


from collections import defaultdict
test_cases = int(input().strip())
for _ in range(test_cases):
	(n, m) = map(int, input().split())
	li = []
	diagonal_sum = defaultdict(int)
	anti_diagonal_sum = defaultdict(int)
	max_ = index = -1
	for i in range(n):
		arr = list(map(int, input().split()))
		li.append(arr)
	for i in range(n):
		for j in range(m):
			diagonal_sum[i - j] += li[i][j]
			anti_diagonal_sum[j + i] += li[i][j]
	for i in range(n):
		for j in range(m):
			max_ = max(max_, diagonal_sum[i - j] + anti_diagonal_sum[j + i] - li[i][j])
	print(max_)


def main():
	T = int(input())
	for test in range(T):
		pos = list(map(int, input().split()))
		n = pos[0]
		m = pos[1]
		grid = []
		for i in range(n):
			grid.append(list(map(int, input().split())))
		main_diagonal_sums = {}
		right_diagonal_sums = {}
		d_diff = n - 1
		d_sum = 0
		while d_diff >= -m + 1:
			i = max(0, d_diff)
			main_sum = 0
			while i < n and i - d_diff < m:
				main_sum += grid[i][i - d_diff]
				i += 1
			main_diagonal_sums[d_diff] = main_sum
			d_diff -= 1
		while d_sum <= n + m - 2:
			i = min(m - 1, d_sum)
			right_sum = 0
			while d_sum - i < n and i >= 0:
				right_sum += grid[d_sum - i][i]
				i -= 1
			right_diagonal_sums[d_sum] = right_sum
			d_sum += 1
		max_sum = 0
		for (i, row) in enumerate(grid):
			for (j, cell) in enumerate(row):
				max_sum = max(max_sum, main_diagonal_sums[i - j] + right_diagonal_sums[i + j] - cell)
		print(max_sum)
main()


rng = int(input())

def x_sum(row, col, matrix):
	to_right = {}
	to_left = {}
	for i in range(row):
		for j in range(col):
			s = i + j
			d = i - j
			if s not in to_left:
				to_left[s] = matrix[i][j]
			else:
				to_left[s] = to_left[s] + matrix[i][j]
			if d not in to_right:
				to_right[d] = matrix[i][j]
			else:
				to_right[d] = to_right[d] + matrix[i][j]
	ans = 0
	for i in range(row):
		for j in range(col):
			ans = max(ans, to_left[i + j] + to_right[i - j] - matrix[i][j])
	print(ans)
for i in range(rng):
	lst = list(map(int, input().split()))
	row = lst[0]
	col = lst[1]
	matrix = []
	for i in range(row):
		temp = list(map(int, input().split()))
		matrix.append(temp)
	x_sum(row, col, matrix)


def BishopMaxAttack(board):
	row = len(board)
	col = len(board[0])
	left_diagonal_sum = {}
	right_diagonal_sum = {}
	for i in range(row):
		for j in range(col):
			left_diagonal_sum[i - j] = left_diagonal_sum.get(i - j, 0) + board[i][j]
			right_diagonal_sum[i + j] = right_diagonal_sum.get(i + j, 0) + board[i][j]
	maxAttack = 0
	for i in range(row):
		for j in range(col):
			maxAttack = max(maxAttack, left_diagonal_sum[i - j] + right_diagonal_sum[i + j] - board[i][j])
	return maxAttack
testcases = int(input())
chessboards = [[] for i in range(testcases)]
for i in range(testcases):
	(m, n) = map(int, input().split())
	for _ in range(m):
		chessboards[i].append(list(map(int, input().split())))
for chess in chessboards:
	print(BishopMaxAttack(chess))


from collections import defaultdict
n = int(input())
for i in range(n):
	(n, m) = list(map(int, input().split()))
	grid = []
	for _ in range(n):
		row = list(map(int, input().split()))
		grid.append(row)
	diagonal1 = defaultdict(int)
	diagonal2 = defaultdict(int)
	for row in range(n):
		for col in range(m):
			diagonal1[row - col] += grid[row][col]
			diagonal2[row + col] += grid[row][col]
	max_value = 0
	for row in range(n):
		for col in range(m):
			curr_value = diagonal1[row - col] + diagonal2[row + col] - grid[row][col]
			max_value = max(max_value, curr_value)
	print(max_value)


from collections import defaultdict
testcase = int(input())
for _ in range(testcase):
	newlist = list(tuple(map(int, input().split())))
	c = newlist[1]
	r = newlist[0]
	grid = []
	for row in range(r):
		eachrow = list(map(int, input().split()))
		grid.append(eachrow)
	diagonal1 = defaultdict(int)
	diagonal2 = defaultdict(int)
	for row in range(len(grid)):
		for col in range(len(grid[0])):
			diagonal1[row - col] += grid[row][col]
	for row in range(len(grid)):
		for col in range(len(grid[0])):
			diagonal2[row + col] += grid[row][col]
	output = 0
	for row in range(len(grid)):
		for col in range(len(grid[0])):
			diag1 = diagonal1[row - col]
			diag2 = diagonal2[row + col]
			output = max(output, diag1 + diag2 - grid[row][col])
	print(output)


T = int(input())
for t in range(T):
	(n, m) = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	left = [0 for i in range(n + m - 1)]
	for i in range(n):
		for j in range(m):
			left[i + j] += arr[i][j]
	right = [0 for i in range(n + m - 1)]
	for i in range(n):
		for j in range(m - 1, -1, -1):
			right[i + (m - j - 1)] += arr[i][j]
	ans = 0
	for i in range(n):
		for j in range(m):
			temp = left[i + j] + right[i + (m - j - 1)] - arr[i][j]
			ans = max(ans, temp)
	print(ans)


t = int(input())
for test_idx in range(t):
	(n, m) = list(map(int, input().split()))
	lines = []
	for _ in range(n):
		line = list(map(int, input().split()))
		lines.append(line)
	diags_r = [0 for _ in range(n + m)]
	diags_l = [0 for _ in range(n + m)]
	for i1 in range(n):
		for i2 in range(m):
			diags_r[i1 + i2] += lines[i1][i2]
			diags_l[i1 - i2 + m - 1] += lines[i1][i2]
	max_value = 0
	for i1 in range(n):
		for i2 in range(m):
			max_value = max(max_value, diags_r[i1 + i2] + diags_l[i1 - i2 + m - 1] - lines[i1][i2])
	print(max_value)


t = int(input())
result = []
for iter in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		matrix.append(list(map(int, input().split())))
	data = {}
	data1 = {}
	for i in range(1, len(matrix)):
		data[0 - i] = matrix[i][0]
		tempx = i
		tempy = 0
		while tempx + 1 < n and tempy + 1 < m:
			data[0 - i] += matrix[tempx + 1][tempy + 1]
			tempx += 1
			tempy += 1
		data1[i + m - 1] = matrix[i][m - 1]
		tempx = i
		tempy = m - 1
		while tempx + 1 < n and tempy - 1 >= 0:
			data1[i + m - 1] += matrix[tempx + 1][tempy - 1]
			tempx += 1
			tempy -= 1
	for i in range(m):
		data[i] = matrix[0][i]
		tempx = 0
		tempy = i
		while tempx + 1 < n and tempy + 1 < m:
			data[i] += matrix[tempx + 1][tempy + 1]
			tempx += 1
			tempy += 1
		data1[i] = matrix[0][i]
		tempx = 0
		tempy = i
		while tempx + 1 < n and tempy - 1 >= 0:
			data1[i] += matrix[tempx + 1][tempy - 1]
			tempx += 1
			tempy -= 1
	maxx = -1
	for i in range(n):
		for j in range(m):
			if data[j - i] + data1[j + i] - matrix[i][j] > maxx:
				maxx = data[j - i] + data1[j + i] - matrix[i][j]
	print(maxx)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = []
	for t in range(n):
		a.append([int(q) for q in input().split()])
	mp1 = {}
	mp2 = {}
	for i in range(n):
		for j in range(m):
			if i - j in mp1:
				mp1[i - j] += a[i][j]
			else:
				mp1[i - j] = a[i][j]
			if i + j in mp2:
				mp2[i + j] += a[i][j]
			else:
				mp2[i + j] = a[i][j]
	ans = 0
	for i in range(n):
		cur = 0
		for j in range(m):
			cur = mp1[i - j] + mp2[i + j] - a[i][j]
			ans = max(ans, cur)
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	maxi = 0
	mat = [list(map(int, input().split())) for i in range(n)]
	x = [0 for i in range(n + m - 1)]
	y = [0 for i in range(n + m - 1)]
	for i in range(n):
		for j in range(m):
			x[i + j] += mat[i][j]
	for i in range(n):
		for j in range(m):
			y[i + j] += mat[i][m - 1 - j]
	for i in range(n):
		for j in range(m):
			maxi = max(x[j + i] + y[m - 1 - j + i] - mat[i][j], maxi)
	print(maxi)


import math

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))
import math
tests = inp()
for i in range(tests):
	(n, m) = inlt()
	grid = []
	d1 = {}
	d2 = {}
	for i in range(n):
		grid.append(inlt())
	for i in range(n):
		for j in range(m):
			if i + j not in d1:
				d1[i + j] = 0
			if i - j not in d2:
				d2[i - j] = 0
			d1[i + j] += grid[i][j]
			d2[i - j] += grid[i][j]
	maximal = -math.inf
	for i in range(n):
		for j in range(m):
			curVal = d1[i + j] + d2[i - j] - grid[i][j]
			maximal = max(maximal, curVal)
	print(maximal)


nb_tests = int(input())
for tests in range(nb_tests):
	(N, M) = map(int, input().split())
	matrice = []
	for _ in range(N):
		matrice.append(list(map(int, input().split())))
	diag = {}
	anti_diag = {}
	for i in range(N):
		for j in range(M):
			if i + j not in diag:
				diag[i + j] = 0
			if i - j not in anti_diag:
				anti_diag[i - j] = 0
			diag[i + j] += matrice[i][j]
			anti_diag[i - j] += matrice[i][j]
	max_value = 0
	for i in range(N):
		for j in range(M):
			max_value = max(diag[i + j] + anti_diag[i - j] - matrice[i][j], max_value)
	print(max_value)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	l = []
	r = []
	for i in range(m):
		s = 0
		j = 0
		k = i
		while j < n and k >= 0:
			s += a[j][k]
			j += 1
			k -= 1
		l.append(s)
	for i in range(1, n):
		s = 0
		j = m - 1
		k = i
		while j >= 0 and k < n:
			s += a[k][j]
			k += 1
			j -= 1
		l.append(s)
	for i in range(m):
		s = 0
		j = 0
		k = i
		while j < n and k < m:
			s += a[j][k]
			j += 1
			k += 1
		r.append(s)
	for i in range(1, n):
		s = 0
		j = 0
		k = i
		while k < n and j < m:
			s += a[k][j]
			k += 1
			j += 1
		r.append(s)
	ans = 0
	for i in range(n):
		for j in range(m):
			c = l[i + j]
			if i > j:
				d = r[m + (i - j) - 1]
			else:
				d = r[j - i]
			ans = max(ans, c + d - a[i][j])
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	mat = [list(map(int, input().split())) for _ in range(n)]
	dur = defaultdict(int)
	dul = defaultdict(int)
	for i in range(n):
		for j in range(m):
			dur[i + j] += mat[i][j]
			dul[i - j] += mat[i][j]
	ans = -float('inf')
	for i in range(n):
		for j in range(m):
			ans = max(ans, dur[i + j] + dul[i - j] - mat[i][j])
	print(ans)


t = int(input())
for z in range(t):
	(n, m) = [int(x) for x in input().split()]
	M = []
	for i in range(n):
		l_row = [int(x) for x in input().split()]
		M.append(l_row)
	ld = []
	for row1 in range(n):
		u = row1
		v = 0
		sumd = 0
		while 0 <= u and v < m:
			sumd += M[u][v]
			u -= 1
			v += 1
		ld.append(sumd)
	for column1 in range(1, m):
		u = n - 1
		v = column1
		sumd = 0
		while 0 <= u and v < m:
			sumd += M[u][v]
			u -= 1
			v += 1
		ld.append(sumd)
	lpd = []
	for column2 in range(m):
		u = n - 1
		v = column2
		sumd = 0
		while 0 <= u and 0 <= v:
			sumd += M[u][v]
			u -= 1
			v -= 1
		lpd.append(sumd)
	for row2 in range(n - 2, -1, -1):
		u = row2
		v = m - 1
		sumd = 0
		while 0 <= u and 0 <= v:
			sumd += M[u][v]
			u -= 1
			v -= 1
		lpd.append(sumd)
	xfac = n - 1
	ans = 0
	for g in range(n):
		rfac = xfac - g
		h = 0
		cfac = g
		while h < m:
			evaluate = lpd[rfac] + ld[cfac] - M[g][h]
			if ans < evaluate:
				ans = evaluate
			cfac += 1
			rfac += 1
			h += 1
	print(ans)