Pixels

You are given an $N \\times N$ matrix of pixels. Color each pixel black or white so that the end result is as pleasant as possible. You are given three kinds of information. For each pixel $(i, j)$, $A_{ij}$ is the bonus you get if you color it white. $B_{ij}$ is the bonus you get if you color it black. For each pair of adjacent pixels (sharing an edge), $C_{ijk}$ is the cost you pay if the two pixels have different colors.

The cost is given for each pixel and each of its four directions. For pixel $(i, j)$, $C_{ij0}$ is the cost when that pixel and $(i - 1, j)$ differ, $C_{ij1}$ is the cost for $(i, j + 1)$, $C_{ij2}$ is the cost for $(i + 1, j)$, and $C_{ij3}$ is the cost for $(i, j - 1)$. If a neighbor is outside the matrix, its cost is still given as 0. $C_{ij0}$ and $C_{(i-1)j2}$ are always equal, and the same symmetry holds for the other directions.

Maximize the sum of $A_{ij}$ over white pixels plus the sum of $B_{ij}$ over black pixels, minus the costs of adjacent pairs with different colors. Each such pair is counted once.

The first line contains $N$. The next $N$ lines each contain $N$ values, where the $j$-th value on line $i$ is $A_{ij}$. In the same format, the next $N$ lines contain $B_{ij}$. Finally, $N \\times N$ lines follow, each with four values $C_{ij0}$, $C_{ij1}$, $C_{ij2}$, $C_{ij3}$. The $((i-1) \\times N + j)$-th of these lines belongs to pixel $(i, j)$.

Print one line containing the maximum possible pleasantness.

$1 \\le N \\le 100$

$1 \\le A_{ij}, B_{ij}, C_{ijk} \\le 100$

The only possible coloring for the optimal pleasantness is:

Black White
Black Black

The cost of coloring $(2, 1)$ and $(2, 2)$ differently is very high, so they should share a color. Black is the better choice for them. For $(1, 1)$ and $(1, 2)$, the better option is clear.