Dual PACMAN Bean Harvest

Two PACMAN start their journey from the bottom‐left corner of a grid and head to the top‐right corner where delicious beans are waiting. The grid is represented as an N×M matrix \(A\), where each cell \(A(i,j)\) contains a nonnegative integer denoting the number of beans in that cell. Initially, both PACMAN are located at cell \((1,1)\) (the bottom‐left cell), and the destination is \((N,M)\) (the top‐right cell).

Each PACMAN can only move either to the right or upward. When a PACMAN visits a cell, it eats the beans there. If both PACMAN pass through the same cell, the beans are collected only once.

The paths chosen by the PACMAN can share common cells (i.e. have intersections) but cannot cross each other. In other words, if we require that at every step the first PACMAN is never strictly above the second PACMAN (i.e. its row index is always less than or equal to that of the second PACMAN), then this ordering must be preserved throughout the journey.

Your task is to determine the maximum total number of beans the two PACMAN can collect together by choosing two valid, non‐crossing paths from \((1,1)\) to \((N,M)\).

Mathematically, if the two paths are denoted by sequences of coordinates \(P_1 = (i_1,j_1), (i_2,j_2), \dots, (N,M)\) and \(P_2 = (k_1,l_1), (k_2,l_2), \dots, (N,M)\) with \( (i_1,j_1) = (k_1,l_1) = (1,1) \), then the condition that the paths do not cross is ensured by requiring \(i \leq k\) at every simultaneous move. The total beans collected is the sum of beans from the union of cells visited by either PACMAN.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \le N, M \le 1000\)), representing the number of rows and columns of the grid respectively. The following \(N\) lines each contain \(M\) nonnegative integers. The grid is provided from the bottom row to the top row, and the integer in each cell represents the number of beans available at that cell.

outputFormat

Output a single integer representing the maximum total beans the two PACMAN can collect together under the given conditions.

sample

3 3
1 2 3
4 5 6
7 8 9

29