Covering Chessboard
Tag(s):

## Medium-Hard

Problem
Editorial
Analytics

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

You can capture grid squares in two different ways.

1. You can directly capture a grid square. This costs ci,j.
2. You can indirectly capture a grid square. You can only do this if we have already captured all of this squares neighbors. This costs bi,jci,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.

### Input format:

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 vi,j.

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

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

### Output format:

Print a single integer, the answer to the problem.

### Constraints

0 ≤ vi,j ≤ 100,000
0 ≤ bi,jci,j ≤ 100,000
1 ≤ n, m

n, m ≤ 3

n, m ≤ 7

n, m ≤ 25

SAMPLE INPUT
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
SAMPLE OUTPUT
13

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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

July Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Greedy Algorithms
• Algorithms > Dynamic Programming
• Math > Combinatorics