Covering Chessboard

★★★★★

14 votes

Graphs, Medium

Details

Problem

You have an n by m grid. Each grid square has a certain value associated with it. This is given by the numbers v_i,j.

You can capture grid squares in two different ways.

You can directly capture a grid square. This costs c_i,j.
You can indirectly capture a grid square. You can only do this if we have already captured all of this squares neighbors. This costs b_i,j ≤ c_i,j.

Two squares are neighbors if they share an edge.

Your score is the sum of values you have captured minus the cost it took to capture those squares. Return the maximum possible score you can achieve.

The first line of input will contain two integers n, m.

The next n lines of input will contain m space separated integers each. The j-th number on the i-th line denotes v_i,j.

The next n lines of input will contain m space separated integers each. The j-th number on the i-th line denotes b_i,j.

The next n lines of input will contain m space separated integers each. The j-th number on the i-th line denotes c_i,j.

Print a single integer, the answer to the problem.

For all subtasks:
0 ≤ v_i,j ≤ 100,000
0 ≤ b_i,j ≤ c_i,j ≤ 100,000
1 ≤ n, m

Subtask 1 (45 pts):
n, m ≤ 3

Subtask 2 (35 pts):
n, m ≤ 7

Subtask 3 (20 pts):
n, m ≤ 25

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

A more human-readable version of the input is as follows:

3 5 9 0 3 2 4 0 2 8 6 2 5 3 4 1 3

5 1 7 9 5 2 4 1 2 4 9 1 2 2 0

9 1 8 9 7 2 7 3 2 9 9 1 9 8 2

The optimal strategy in this case is to directly capture the following squares:

O X O O O
X O X X O
O X O O X

And indirectly capture only the top left square.