Background

JYY bought a huge rectangular piece of land on Mars for real estate development. Because the land was too large, JYY divided it into an $N$ by $M$ grid of small squares and built a house in each cell. After many years, the development was finally completed, and JYY could put these houses up for sale. Now he has found two unusual rich buyers: Nannan and Qiangqiang.

The troublesome part is that Nannan and Qiangqiang cannot get along at all. To make sure they do not conflict, JYY needs to separate the houses sold to them with walls. However, building walls costs money. As an expert in reselling land, JYY naturally wants to earn as much money as possible, so he invites you to help him design the best selling plan.

Problem Description

JYY divides the land into an $N$ by $M$ rectangle, and builds a house in each cell. Now, Nannan and Qiangqiang have submitted their purchase intentions to JYY. For each house, they have given their bids (either not buying, or buying at a certain price). Also, since they have already agreed on their respective territories, there is no case where both of them want to buy the same house.

JYY may choose whether to sell each house (since they never both want the same house, if JYY decides to sell a house, its buyer is determined). After selling houses to Qiangqiang and Nannan, JYY obtains the sum of the bids of all sold houses.

However, as after-sales service, JYY must completely separate their houses by building walls (placing a wall between two adjacent houses). “Completely separate” means that the built walls together with the boundary walls divide the whole area into several disconnected parts, and in each part there are houses belonging to only one person. Of course, building walls costs money, and it is expensive. But JYY claimed in advertising that walls would be totally free, so he has to pay this cost himself.

JYY asks you to decide which houses to sell and which walls to build, so that the revenue from selling houses minus the cost of building walls is maximized. Another piece of good news is that the entire boundary of the land already has walls, so JYY can use these existing walls to achieve the goal. The figure below is an example where walls partition the area into $3$ disconnected parts. The numbers inside cells represent bids (see the input format for their meaning), and the values on edges represent wall-building costs. The boundary walls already exist and do not require any extra cost.

Input Format

The first line contains two natural numbers $N$ and $M$ separated by spaces.

The next $N$ lines each contain $M$ integers. The integer $a$ in row $i$, column $j$ describes the selling information of the house at $(i, j)$. If $a = 0$, it means that neither Qiangqiang nor Nannan wants to buy this house. If $a > 0$, it means Qiangqiang wants to buy this house at price $a$. If $a < 0$, it means Nannan wants to buy this house at price $-a$.

The next $N - 1$ lines each contain $M$ integers. The number in row $i$, column $j$ is the cost to build a wall between the house at row $i$, column $j$ and the house at row $i + 1$, column $j$.

The next $N$ lines each contain $M - 1$ integers. The number in row $i$, column $j$ is the cost to build a wall between the house at row $i$, column $j$ and the house at row $i$, column $j + 1$.

Output Format

Output a single line containing one integer, which is JYY’s maximum profit.

5 5
-3 7 0 0 0
8 0 7 -10 0
0 7 0 1 0
0 0 0 0 0
-8 0 0 2 10
4 50 50 1 50
50 50 1 9 50
50 50 1 1 50
2 50 50 50 50
2 50 50 50
50 50 1 1
50 1 8 1
50 50 50 50
1 50 50 50

48

Hint

For $100\%$ of the testdata, $1 \leq N, M \leq 200$, and any price does not exceed $1000$.

Translated by ChatGPT 5