Maximizing Grid Profit with Fencing Cost

Pear has landed on planet X and divided a plain into an M×N grid. Each cell has an integer value (which can be positive or negative) representing its profit. To evaluate the potential of the land, Pear wishes to select a subset of the grid cells and enclose them by building fences. The fences run along the grid lines. In an M×N grid there are \((M+1)\times N+M\times (N+1)\) fence segments. Note that fence segments on non‐boundary lines are shared by two adjacent cells.

When you select a set of cells, you must build fences on every grid edge separating a selected cell from an unselected cell or from the outside. In other words, if a cell on the border is selected, you must also fence the outer boundary of that cell. (A selected set may be disconnected and may even have holes – any “hole” is treated as a separate region that must be fenced off as well.)

The cost to build each fence segment is a given positive integer F. Thus, if a cell is selected it incurs a fixed cost equal to the sum of F for each of its boundaries that touch an unselected cell or the grid boundary. Meanwhile, each selected cell produces a profit equal to its cell value. Pear’s goal is to choose a set of cells and build the required fences such that the net profit is maximized. The net profit is defined as:

[ \text{Net Profit} = \sum_{(i,j)\in S} \text{value}_{ij} ; - ; \text{(Total fence cost)} ]

You are given the grid, where the first input line contains three integers: M, N, and F. The next M lines each contain N integers representing the grid cell values. If you decide not to select any cell, the net profit is 0.

Note: It can be shown that the optimal solution can be found by reducing the problem to a minimum cut formulation on a graph constructed as follows:

• For each cell, define a penalty that is incurred if the cell is selected. This penalty corresponds to the fencing required along the border boundaries of the cell. For a cell, for each side that is on the grid boundary, add a cost of F.
• For each adjacent pair of cells (sharing a common edge), if one is selected and the other is not, an extra cost of F is incurred. This is modeled by adding an edge between the two cell nodes with capacity F (in both directions).
• Each cell’s net contribution is its value minus its border penalty. These contributions are then connected to the source or sink depending on whether they are positive or negative.

The maximum net profit is given by the sum of the positive contributions minus the minimum cut value.

inputFormat

The first line contains three integers M N F (the number of rows, the number of columns, and the cost per fence segment, respectively).

Then follow M lines, each containing N integers. The j-th integer in the i-th line represents the profit value of the cell at position (i, j).

outputFormat

Output a single integer representing the maximum net profit that can be achieved.

sample

2 2 1
1 2
-3 4

0