Maximizing Profit with House Sales and Wall Construction

JYY has divided a plot of land into a grid of N rows and M columns. In each cell a house is built. Two interested parties, NanNan and QiangQiang, have each submitted a bid for every house. Due to prior coordination, no house is bid on by both people simultaneously. That is, for each house a bid is given by at most one of them. For a house whose bid is non‐negative, the bid is from NanNan and if the bid is negative then its absolute value is the bid from QiangQiang.

JYY can decide for each house whether or not to sell it. If a house is sold its buyer is predetermined by the bid (NanNan if the bid is non‐negative; QiangQiang if the bid is negative) and JYY obtains the sale price (if the bid is negative, the revenue is the absolute value of the bid). However, as after‐sale service, JYY must build walls between houses so that the houses of the two buyers are completely separated. The separation requirement means that the walls built (plus the fixed external boundary walls) partition the whole grid into several connected regions, and every region that contains at least one sold house contains houses bought by only one of the two buyers.

A wall can be built along any common edge between two adjacent houses at a given cost. (The outer borders already have walls and do not cost extra.)

JYY wants to choose which houses to sell and along which edges to build walls so that his net profit (the total sale revenue minus the total wall‐construction cost) is maximized.

Input/Output note: It turns out that an optimal strategy always involves building walls only between two adjacent houses that are sold to different buyers. In other words, if we define a cell i having a choice to be sold or not sold, and if sold its buyer is fixed by the sign of the bid, then the extra cost is incurred only along an edge connecting a cell sold to NanNan and a cell sold to QiangQiang. Moreover, unsold cells can be assigned arbitrarily to a buyer’s region without extra cost. With some thought, one may reduce the decision to choosing a subset of houses to sell in such a way that the net profit

[ \text{Profit} = \sum_{i\in S_A} a_i + \sum_{j\in S_B} b_j - \sum_{\substack{(i,j)\text{ adjacent}
i \in S_A,, j \in S_B}} c_{ij} ]

is maximized, where for a house with bid x, if x ≥ 0 then it is a candidate for NanNan with profit a = x, and if x < 0 then it is a candidate for QiangQiang with profit b = |x|; and c_ij is the cost of building a wall along the edge that lies between cells i and j.

This problem can be solved by modeling it as a minimum cut / maximum flow problem on a graph constructed as follows. For every cell with a non‐negative bid (a candidate for NanNan) create a node and add an edge from the source to this node with capacity equal to its bid. For every cell with a negative bid (a candidate for QiangQiang) create a node and add an edge from it to the sink with capacity equal to the absolute value of its bid. For every edge between two adjacent cells where one is a candidate for NanNan and the other for QiangQiang, add an edge from the NanNan node to the QiangQiang node with capacity equal to the cost for building a wall along that shared edge. Then the answer is the total potential revenue (i.e. the sum of all positive bids plus the absolute value of all negative bids) minus the minimum cut value of the resulting network.

inputFormat

The first line contains two space‐separated integers N and M (1 ≤ N, M ≤ 50) indicating the number of rows and columns.

The next N lines each contain M integers. The j^th integer in the i^th line is x, the bid for the house in row i, column j. If x ≥ 0, the bid is from NanNan; if x < 0, then the absolute value is the bid from QiangQiang.

The following N lines describe the horizontal wall-construction costs. The i^th of these lines contains M-1 integers. The j^th integer on this line is the cost of building a wall between the house at row i, column j and the house at row i, column j+1.

The next N-1 lines describe the vertical wall-construction costs. Each of these lines contains M integers. In the i^th of these lines, the j^th integer is the cost of building a wall between the house at row i, column j and the house at row i+1, column j.

You may assume all bids and wall costs are integers, and wall costs are positive.

outputFormat

Output a single integer: the maximum net profit JYY can achieve—that is, the total sale revenue minus the total wall construction cost under an optimal plan.

sample

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

11