P7872 "Wdoi-4" Satori Onee-chan and Koishi Imouto

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.

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.

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 one line, indicating the maximum enjoyment Koishi can obtain for this testdata.

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