Description

In an $n\times m$ grid, each cell contains two types of minerals: yeyenum and bloggium, and the amount of each in every cell is known. There is a collection station for bloggium at the northern edge, and a collection station for yeyenum at the western edge. You must install a conveyor belt in each cell that points either north or west (each cell can have only one direction). What is the maximum total amount of minerals that can be collected?

Input Format

The first line contains two integers $n,m,\ ( 1 ≤ n ≤ 500, 1 ≤ m ≤ 500)$. Then follow $n$ lines and $m$ columns giving, for each cell, the amount that can be transported as yeyenum (each value is less than $1000$). After that, another $n$ lines and $m$ columns follow, giving the amount that can be transported as bloggium for each cell. The input ends when $n, m$ are both $0$.

Output Format

For each test case, output a single integer: the maximum total amount of minerals that can be collected.

4 4
0 0 10 9 
1 3 10 0
4 2 1 3 
1 1 20 0 
10 0 0 0 
1 1 1 30 
0 0 5 5 
5 10 10 10 
0 0

98

Hint

During transportation, turning is not allowed; items can only travel in a straight line.

Translated by ChatGPT 5