It's late at night, and the college students are required to return to their college hostels from the hostel garden.

The hostel garden is a rectangular field of dimensions N \times M, with two hostels — one across the left edge and one across the top edge of the field.

Students are currently in the cells of the field. You are given two matrices of size N \times M, A and B. A_{i, j} denotes the number of students currently in the i^{th} row and the j^{th} column of the field who want to reach the hostel along the left edge of the field, and similarly B_{i, j} denotes the number of students currently in the i^{th} row and the j^{th} column of the field who want to reach the hostel along the top edge of the field.

Students will always move toward their respective hostels as a straight path from their positions (so the students represented by A will always move straight left, and those represented by B will always move straight up), and are allowed to enter the hostel from any cell adjacent to the edge of the field (i.e., there are no specific entry points for the hostels).

There is only one restriction: there should not exist two students such that one of them reaches the left-edge hostel, the other one reaches the top-edge hostel, and the paths followed by these two students intersect.

For example, it is not allowed for a student in cell (1, 5) to go left and a student in cell (28, 3) to go up, because their paths would intersect at cell (1, 3).

Under this restriction, what is the maximum number of students who can reach their hostels?

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

- The first line of input will contain a single integer T, the number of test cases. Then the testcases follow.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N, M.
- The next N lines describe the matrix A. The i-th of these N lines contains M space-separated integers A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}
- The next N lines describe the matrix B. The i-th of these N lines contains M space-separated integers B_{i, 1}, B_{i, 2}, \ldots, B_{i, M}

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

For each test case, output in a single line the maximum number of students who can reach their hostels.

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

$1 ≤ T ≤ 10^{6}$
$1 ≤ N, M ≤ 10^{6}$
$0 ≤ A_{i, j} < 10^{9}$
$0 ≤ B_{i, j} < 10^{9}$
- The sum of $N\times M$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
2
1 3
6 7 0
9 1 0
2 2
89 0
67 99
12 44
23 54
----- Sample Output 1 ------ 
13
299

----- explanation 1 ------ 
Test case $1$: It is optimal to move all students of the left-edge hostel, hence the answer is $6+7+0=13$.

Test case $2$: It is optimal to move the students of (row, column)=$(1,2)$ to the top-edge hostel, and students from the remaining cells to move to the left-edge hostel, therefore the answer is $44+89+67+99=299$.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Range queries


Solutions:
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	A = [[0 for i in range(m)] for j in range(n)]
	B = [[0 for i in range(m)] for j in range(n)]
	for i in range(n):
		A[i] = list(map(int, input().split()))
	for i in range(n):
		B[i] = list(map(int, input().split()))
	for i in range(n - 2, -1, -1):
		for j in range(m):
			A[i][j] += A[i + 1][j]
	for i in range(1, n):
		for j in range(m):
			B[i][j] += B[i - 1][j]
	dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for col in range(m - 1, -1, -1):
		for row in range(n, -1, -1):
			if col < m - 1:
				dp[row][col] += dp[row][col + 1]
			if row:
				dp[row][col] += B[row - 1][col]
			if row < n:
				dp[row][col] += A[row][col]
				dp[row][col] = max(dp[row][col], dp[row + 1][col])
	print(dp[0][0])


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

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())

def pprint(matrix):
	for i in range(len(matrix)):
		print(*matrix[i])
t = int(input())
for _ in range(t):
	(n, m) = integer_list()
	A = [integer_list() for i in range(n)]
	B = [integer_list() for i in range(n)]
	students = [[[0, 0] for _ in range(m)] for i in range(n)]
	students[0][0][0] = B[0][0]
	students[0][0][1] = A[0][0]
	cumm_top = []
	cumm_left = []
	for i in range(n):
		temp = []
		s = 0
		for j in range(m):
			s += A[i][j]
			temp.append(s)
		cumm_left.append(temp)
	for j in range(m):
		temp = []
		s = 0
		for i in range(n):
			s += B[i][j]
			temp.append(s)
		cumm_top.append(temp)
	cumm_top = [list(i) for i in zip(*cumm_top)]
	prev_top = 0
	for i in range(1, m):
		students[0][i][0] = max(students[0][i - 1]) + B[0][i]
		students[0][i][1] = cumm_left[0][i]
	prev_left = 0
	for i in range(1, n):
		students[i][0][0] = cumm_top[i][0]
		students[i][0][1] = max(students[i - 1][0]) + A[i][0]
	for i in range(1, n):
		for j in range(1, m):
			students[i][j][0] = cumm_top[i][j] + max(students[i][j - 1])
			students[i][j][1] = cumm_left[i][j] + max(students[i - 1][j])
	print(max(students[n - 1][m - 1]))


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	(a, b) = ([], [])
	for _ in range(x):
		a.append(list(map(int, input().split())))
	for _ in range(x):
		b.append(list(map(int, input().split())))
	for i in range(x):
		(temp1, temp2) = (0, 0)
		for j in range(y):
			a[i][j] = a[i][j] + temp1
			b[i][j] = b[i][j] + temp2
			(temp1, temp2) = (a[i][j], b[i][j])
	ans = [[0 for _ in range(y + 1)] for _ in range(x)]
	for i in range(x):
		for j in range(y + 1):
			if j == 0:
				ans[i][j] = b[i][-1]
				if i != 0:
					ans[i][j] = ans[i][j] + ans[i - 1][j]
			elif j == y:
				if i == 0:
					ans[i][j] = max(a[i][-1], ans[i][j - 1])
				else:
					ans[i][j] = max(a[i][-1] + ans[i - 1][j], ans[i][j - 1])
			else:
				ans[i][j] = max(ans[i - 1][j] + (b[i][-1] - b[i][j - 1]) + a[i][j - 1], ans[i][j - 1])
	print(ans[-1][-1])


import random
import math
from collections import defaultdict, Counter
from functools import lru_cache
import bisect
import heapq

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def google(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	b = []
	for i in range(n):
		b.append(list(map(int, input().split())))
	dp = [[0 for i in range(m + 1)] for _ in range(n)]
	for i in range(n - 1, -1, -1):
		maxv = 0
		su = 0
		for j in range(m):
			maxv += a[i][j]
			su += a[i][j]
		dp[i][-1] = maxv
		if i < n - 1:
			dp[i][-1] += dp[i + 1][-1]
		for j in range(m - 1, -1, -1):
			su -= a[i][j]
			su += b[i][j]
			aa = su + (dp[i + 1][j] if i < n - 1 else 0)
			bb = dp[i][j + 1]
			dp[i][j] = max(aa, bb)
	print(dp[0][0])
for t in range(int(input())):
	solve()


import sys
sys.setrecursionlimit(10 ** 7)

def f(i, j):
	if i >= n:
		return 0
	if j > m:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	case1 = pref[i][j] + suff[i][j] + f(i + 1, j)
	case2 = f(i, j + 1)
	dp[i][j] = max(case1, case2)
	return dp[i][j]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(list(map(int, input().split())))
	b = []
	for _ in range(n):
		b.append(list(map(int, input().split())))
	pref = [[0 for i in range(m)] for j in range(n)]
	suff = [[0 for i in range(m)] for j in range(n)]
	for i in range(n):
		pref[i][0] = a[i][0]
		for j in range(1, m):
			pref[i][j] = a[i][j] + pref[i][j - 1]
		pref[i] = [0] + pref[i]
	for i in range(n):
		suff[i][m - 1] = b[i][m - 1]
		for j in range(m - 2, -1, -1):
			suff[i][j] = b[i][j] + suff[i][j + 1]
		suff[i].append(0)
	dp = [[-1 for _ in range(m + 1)] for _ in range(n)]
	print(f(0, 0))