Maximizing Traveler Joy in the DiLing Palace

The DiLing Palace can be seen as an n×m grid of rooms. The room at position \((i,j)\) contains an object with an integer novelty value \(w_{i,j}\) (which can be negative). The joy of Komeiji Koito (\(\text{恋}\)) is defined as the sum of the novelty values of all objects she sees during her journey.

Before Koito begins her journey, Komeiji Satori (\(\text{觉}\)) cleans the palace. She starts at \((1,1)\) and moves to \((x_s,y_s)\) by only moving right or down. In each room she visits, she may pick up the object there and may also deposit an arbitrary number (possibly zero) of objects from her bag into that room. She can both pick up and deposit objects in the same room. However, because she does not want to remove any objects from the palace, her bag must be empty when she finishes cleaning at \((x_s,y_s)\).

After cleaning, Koito starts her journey at \((1,1)\) and moves to \((x_k,y_k)\) (again, only moving right or down). In every room she visits she collects all the objects present in the room; thus, she obtains the total novelty equal to the sum of these objects’ values.

Since Satori can rearrange objects along her cleaning path, she can, for example, remove objects with negative novelty from rooms that Koito will visit and concentrate objects with positive novelty into one common cell along a path both will share. In other words, Satori chooses a cleaning route (from \((1,1)\) to \((x_s,y_s)\)) and picks up every object with a positive novelty (by taking \(\max(w,0)\) from each room along her path). Later, she can deposit the collected objects into one common room that lies on both her cleaning route and Koito’s travel route so that the traveler’s sum is increased. Koito, on her part, chooses a travel route (from \((1,1)\) to \((x_k,y_k)\)) whose total original novelty sum is given by the standard right‐and‐down path sum. However, in the one room where Satori deposits her collected objects, Koito will obtain the original object value replaced by the sum of all positive objects Satori managed to pick up along her cleaning path.

Your task is to compute the maximum total joy (novelty sum) that Koito can obtain by an appropriate choice of Satori’s cleaning route and Koito’s travel route. Formally, if we denote by \(A(i,j)\) the maximum sum along a valid travel route from \((1,1)\) to \((x_k,y_k)\) that goes through a common cell \((i,j)\) (computed as the sum from start to \((i,j)\) plus the sum from \((i,j)\) to \((x_k,y_k)\) minus \(w_{i,j}\)), and by \(C(i,j)\) the maximum sum of positive values along a valid cleaning route from \((1,1)\) to \((x_s,y_s)\) that passes through \((i,j)\) (with each room contributing \(\max(w_{i,j},0)\)), then the answer is:

[ \max_{1\le i\le \min(x_s,x_k),;1\le j\le \min(y_s,y_k)} \Bigl{ A(i,j) - w_{i,j} + C(i,j) \Bigr}. ]

Note: The moves allowed on both routes are only to the right or down. Both routes always start at \((1,1)\). The cleaning route ends at \((x_s,y_s)\) and the travel route ends at \((x_k,y_k)\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n,m \leq 10^3)\) representing the number of rows and columns of the grid. The second line contains four integers \(x_s,y_s,x_k,y_k\) where \(1 \le x_s \le n\), \(1 \le y_s \le m\), \(1 \le x_k \le n\) and \(1 \le y_k \le m\). It is guaranteed that the cleaning endpoint \((x_s,y_s)\) and travel endpoint \((x_k,y_k)\) are within the grid.

Then follow \(n\) lines, each containing \(m\) integers. The \(j\)-th integer in the \(i\)-th line is \(w_{i,j}\) \( (|w_{i,j}| \leq 10^9) \), the novelty value of the object in room \((i,j)\).

outputFormat

Output a single integer — the maximum total novelty (joy) that Koito can obtain.

sample

3 3
3 3 3 3
1 -2 3
-4 5 -6
7 -8 9

24