Conveyor Belt Mineral Collection

You are given an \(n \times m\) grid. Each cell \((i,j)\) contains two kinds of minerals: yeyenum and bloggium. The amount of yeyenum and bloggium in cell \((i,j)\) are given by A_i,j and B_i,j respectively.

Along the north border (i.e. row 1) there is a collection station for bloggium, and along the west border (i.e. column 1) there is a collection station for yeyenum. In every cell you must install a conveyor belt which can be oriented either to the north or to the west. However, the following rule applies for a mineral to be successfully collected:

• If a cell \((i,j)\) installs a north-oriented belt, it will transport its own bloggium. But the mineral will be successfully delivered only if every cell in column \(j\) from row 1 to row \(i\) also has a north-oriented belt. In other words, in column \(j\) the top contiguous block of cells (starting from row 1) that are all north-oriented will have their bloggium delivered.
• If a cell \((i,j)\) installs a west-oriented belt, it will transport its own yeyenum. It is successfully collected only if every cell in row \(i\) from column 1 to column \(j\) also has a west-oriented belt. That is, in row \(i\) the leftmost contiguous block of cells (starting from column 1) that are all west-oriented will have their yeyenum delivered.

Since every cell must install exactly one belt, the only choices are whether to use north or west in that cell. Observe that in order for the conveyor chains to be unbroken, the choices in each row must follow a pattern. Specifically, if in a row you decide that the first k cells (columns 1 to \(k\)) use a west belt and the remaining cells (columns \(k+1\) to \(m\)) use a north belt, then the delivery condition in that row is automatically satisfied. However, notice that the north delivery in a given column depends on all rows above. For a north delivery to succeed in column \(j\) for a cell in row \(i\), every row from 1 to \(i\) must have chosen a split index strictly less than \(j\). In other words, if we denote by \(p_i\) the number of west‐oriented cells (from the left) in row \(i\) (so that cells \((i,1)\) to \((i,p_i)\) are west and the rest are north), then a necessary and sufficient condition for a valid overall configuration is that the sequence \(p_1, p_2, \dots, p_n\) is non‐decreasing (i.e. \(p_1 \le p_2 \le \cdots \le p_n\)).

For a given row \(i\) and a choice \(p_i = k\) (with \(0 \le k \le m\), where \(k=0\) means all cells in that row are north, and \(k=m\) means all are west), the contribution from row \(i\) is:

\[ \text{Row}_i = \sum_{j=1}^{k} A_{i,j} \;\; (\text{yeyenum collected}) \quad+\quad \sum_{j=k+1}^{m} B_{i,j} \;\; (\text{bloggium collected}). \]

Your task is to choose a non‐decreasing sequence \(p_1, p_2, \dots, p_n\) (with \(0 \le p_i \le m\)) to maximize the total collected mineral, which is the sum over all rows of their contributions.

Input and output format are described below. All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns).

The next \(n\) lines each contain \(m\) integers. The \(i\)-th of these lines gives the values \(A_{i,1}, A_{i,2}, \dots, A_{i,m}\) (the amounts of yeyenum in the cells of row \(i\)).

The following \(n\) lines each contain \(m\) integers. The \(i\)-th of these lines gives the values \(B_{i,1}, B_{i,2}, \dots, B_{i,m}\) (the amounts of bloggium in the cells of row \(i\)).

outputFormat

Output a single integer, the maximum total amount of minerals that can be collected following the rules.

sample

2 2
1 2
3 4
5 6
7 8

26