Background

Komeiji Satori and Komeiji Koishi are satori youkai living in Chireiden. Komeiji Satori has the ability to read minds, but her younger sister Komeiji Koishi does not.

Chireiden is a very spacious large villa-like building in the upper part of Former Hell. Because of this, Koishi often explores Chireiden to find fun and interesting things. Chireiden can be divided into many, many rooms, and each room contains one ornament. In Koishi’s eyes, each ornament has a “novelty value” (in particular, the novelty value may be negative, meaning Koishi finds the item extremely boring).

One day, Koishi, who likes wandering around, wanted to explore the entire Chireiden. As her older sister, Satori naturally does not want Koishi to be disappointed. That is, Satori can improve Koishi’s overall enjoyment during the visit (i.e., the sum of novelty values of all items Koishi sees) by moving items between rooms.

However, Satori is not good at exercising, so she will not walk a long distance. What you need to do is to tell Satori the maximum possible enjoyment Koishi can obtain after Satori’s rearrangement.

Problem Description

Chireiden can be viewed as a matrix of rooms with size $n\times m$. We use $(x,y)$ to describe the position of a room. The novelty value of the item in room $(i,j)$ is $w_{i,j}$, represented by an integer (possibly negative). Koishi’s enjoyment is defined as the sum of novelty values of all items she sees.

While cleaning, Satori will walk from $(1,1)$ to $(x_s,y_s)$. During this process, Satori can only move to the room below or to the right (suppose Satori is currently at $(i,j)$, then her next step can only be to $(i+1,j)$ or $(i,j+1)$, and she will not walk outside Chireiden). When Satori reaches a room, she may pick up the item in the room and put it into her backpack; she may also take out any number of items from the backpack and place them in the room (she may both pick up and place items). Of course, Satori does not want to take any items out of Chireiden, so when the cleaning ends, Satori’s backpack should contain no items. Initially, the backpack is empty.

After that, Koishi will walk from $(1,1)$ to $(x_k,y_k)$ for her trip. Koishi will see all items in a room and gain the corresponding novelty value. Same as Satori, Koishi also only moves to the room below or to the right.

Satori wants to know, under these rules, what is the maximum final enjoyment Koishi can obtain.

Input Format

The first line contains two positive integers $n,m$, describing the size of the rooms in Chireiden.
Next $n$ lines follow, each containing $m$ integers. The $j$-th integer in the $i$-th line, $w_{i,j}$, describes the novelty value of the item in room $(i,j)$.
The next line contains four positive integers $x_s,y_s,x_k,y_k$ in order, with the same meanings as in the statement, representing the ending positions of Satori and Koishi.

Output Format

Output one line, indicating the maximum enjoyment Koishi can obtain for this testdata.

4 4
0 4 5 3
3 2 -1 2
-1 3 -3 -1
0 4 2 4
3 3 4 4

22

8 8
46 90 58 59 33 64 66 93
52 25 91 51 96 11 21 6
11 1 68 25 50 90 86 94
73 83 48 80 46 46 81 16
60 61 80 55 83 97 67 47
78 96 59 96 39 7 94 66
29 68 15 61 69 43 7 38
31 29 67 79 71 17 0 97
5 3 2 5

509

Hint

Sample $3$ can be found in the attached files $\textbf{\textit{koishi3.in}/\textit{koishi3.out}}$.

Sample Explanation

Sample 1 Explanation

• Satori’s walking path is $(1,1)\to(2,1)\to(2,2)\to(2,3)\to(3,3)$. The novelty values of the items she encounters are $0,3,2,-1,-3$. During the process, she places the item of value $3$ picked up at $(2,1)$ into $(2,2)$.
• Koishi’s walking path is $(1,1)\to(1,2)\to(2,2)\to(3,2)\to(4,2)\to(4,3)\to(4,4)$. The novelty values of the items she sees are $0,4,2+3,3,4,2,4$. The total enjoyment is $22$.

It can be proven that there is no better plan.

Constraints and Notes

• For the first $10\%$ of the data, $1\le n,m\le 3;|w_{i,j}|\le 10$.
• For the first $30\%$ of the data, $1\le n,m\le 5;|w_{i,j}|\le 10^2$.
• For the first $60\%$ of the data, $1\le n,m\le 70;|w_{i,j}|\le 10^5$.
• Another $15\%$ of the data guarantees that $w_{i,j}$ are non-negative integers.
• For $100\%$ of the data, $1\le n,m\le 300;|w_{i,j}|\le 10^6$.

Translated by ChatGPT 5