P2380 Gou-ge's Mining

It is another calm Chinese class. Gou-ge (pinyin) was bored and came up with this problem.

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?

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$.

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

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