Maximizing Dual Paper Note Communication

In a class activity, students are seated in an m×n matrix. Two friends, Xiaoyuan and Xiaoxuan, sit at opposite ends of the diagonal of the matrix: Xiaoyuan at the top‐left cell (1,1) and Xiaoxuan at the bottom‐right cell (m,n). Because they cannot speak directly, they communicate by passing a note. However, the note from Xiaoyuan to Xiaoxuan can only be passed downward or to the right and the reply from Xiaoxuan to Xiaoyuan can only be passed upward or to the left.

Every student in the class (except Xiaoyuan and Xiaoxuan whose goodwill values are defined as 0) is willing to help pass the note only once. That is, if a student helps in one direction, they will not help in the reverse. Each student has a goodwill value — an integer from 0 to 100 — indicating how kind‐hearted they are. The aim is to select two valid passing paths (one in each direction) such that the total sum of the goodwill values of the assisting students (each counted only once even if a cell appears on both paths) is maximized.

Note that if a cell is visited by both paths, its goodwill value is only counted once. Effectively, you are required to find two vertex‐disjoint paths (except the starting and ending cells) from (1,1) to (m,n) with moves constrained as above, such that the sum of values on these paths is maximum. This can be formulated as a Cherry Pickup style problem with appropriate restrictions.

All formulas in this problem are to be written in LaTeX. For instance, the cell coordinates are given as \((1,1)\) for the top–left and \((m,n)\) for the bottom–right, and the matrix size is \(m \times n\).

inputFormat

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

Each of the following \(m\) lines contains \(n\) integers, where each integer (in the range \([0,100]\)) represents the goodwill of the student at that position. Note that the values for the positions (1,1) and (m,n) will be given as 0.

outputFormat

Output a single integer representing the maximum total goodwill achievable by selecting two valid note‐passing paths.

sample

3 3
0 1 2
3 4 5
6 7 0

24