픽셀

$N \\times N$ 크기의 픽셀 행렬이 주어진다. 각 픽셀을 검은색 또는 흰색으로 칠해서 최종 결과의 쾌적도가 최대가 되도록 하라. 주어지는 정보는 세 가지다. 픽셀 $(i, j)$를 흰색으로 칠하면 $A_{ij}$의 보너스를 얻고, 검은색으로 칠하면 $B_{ij}$의 보너스를 얻는다. 변을 공유하는 인접 픽셀 쌍의 색이 다르면 $C_{ijk}$의 비용을 지불한다.

비용은 픽셀마다 네 방향에 대해 주어진다. 픽셀 $(i, j)$에서 $C_{ij0}$는 $(i - 1, j)$ 픽셀과 색이 다를 때의 비용, $C_{ij1}$은 $(i, j + 1)$과, $C_{ij2}$는 $(i + 1, j)$와, $C_{ij3}$는 $(i, j - 1)$과 색이 다를 때의 비용이다. 행렬 밖으로 나가는 방향의 비용도 0으로 주어진다. $C_{ij0}$와 $C_{(i-1)j2}$는 항상 같으며, 다른 방향도 같은 대칭 관계다.

흰색 픽셀의 $A_{ij}$ 합과 검은색 픽셀의 $B_{ij}$ 합을 더하고, 색이 다른 인접 쌍의 비용 합을 뺀 값을 최대화하라. 각 쌍은 한 번만 계산한다.

첫 줄에 $N$이 주어진다. 이어서 $N$줄에 걸쳐 각 줄마다 $N$개의 값이 주어지며, $i$번째 줄의 $j$번째 값이 $A_{ij}$다. 같은 형식으로 $N$줄에 걸쳐 $B_{ij}$가 주어진다. 마지막으로 $N \\times N$줄에 걸쳐 각 줄에 네 개의 값 $C_{ij0}$, $C_{ij1}$, $C_{ij2}$, $C_{ij3}$가 주어진다. $((i-1) \\times N + j)$번째 줄이 픽셀 $(i, j)$의 값이다.

최적 쾌적도의 최댓값을 한 줄에 출력한다.

$1 \\le N \\le 100$

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

최적 쾌적도를 얻는 색칠은 다음이 유일하다.

검은색 흰색
검은색 검은색

$(2, 1)$과 $(2, 2)$를 다른 색으로 칠하는 비용이 매우 크다. 따라서 두 픽셀은 같은 색이어야 하며, 그 색은 검은색이 더 낫다. $(1, 1)$과 $(1, 2)$는 어떤 색이 더 나은지 분명하다.