튜브 마스터 III

팡 교수는 "Tube Master"라는 게임을 하고 있다. 게임 필드는 $(n + 1) \times m$개의 가로 튜브와 $n \times (m + 1)$개의 세로 튜브로 $n \times m$개의 칸으로 나뉜다. 곱 $nm$은 짝수이다. 튜브가 교차하는 점은 $(n + 1)(m + 1)$개이며, 2차원 좌표는 $(i, j)$ ($1\le i\le n+1$, $1\le j\le m+1$)이다. 좌표가 $(i, j)$인 교차점을 "교차점 $(i, j)$"라고 부른다. 교차점 $(i, j), (i+1, j), (i, j+1), (i+1, j+1)$을 꼭짓점으로 하는 칸을 "칸 $(i, j)$"라고 부른다 ($1\le i\le n$, $1\le j\le m$). 각 칸 $(i, j)$에는 정수 ${count}_{i, j}$가 적혀 있다.

위 그림은 $n = 3$, $m = 2$인 게임 필드이다.

팡 교수는 튜브 일부를 사용하려고 한다. 게임에는 다음 제약이 있다.

1. 각 교차점에 연결된 튜브 중 0개 또는 2개만 사용한다.
2. 칸 $(i, j)$에 인접한 회전점은 정확히 ${count}_{i, j}$개이다. 회전점은 가로 튜브 1개와 세로 튜브 1개가 연결된 교차점이다. 교차점 $(x, y)$가 칸 $(i, j)$의 꼭짓점이면 회전점 $(x, y)$는 칸 $(i, j)$에 인접한다.

교차점 $(i, j)$와 $(i, j+1)$을 잇는 튜브를 사용하면 $a_{i, j}$의 비용이 든다. 교차점 $(i, j)$와 $(i+1, j)$를 잇는 튜브를 사용하면 $b_{i, j}$의 비용이 든다. 제약을 모두 만족하면서 총 비용이 최소가 되는 튜브 집합을 찾아라.

첫 줄에 테스트 케이스의 수를 나타내는 양의 정수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$, $m$ ($1 \leq n, m \leq 100$)이 공백으로 구분되어 주어진다.

이어지는 $n$개의 줄에는 각각 $m$개의 정수 ${count}_{i, 1}, {count}_{i, 2}, \dots, {count}_{i, m}$ ($0 \leq {count}_{i, j} \leq 4$)이 공백으로 구분되어 주어진다.

이어지는 $n+1$개의 줄에는 각각 $m$개의 정수 $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ ($1 \leq a_{i, j} \leq 10^9$)이 공백으로 구분되어 주어진다.

이어지는 $n$개의 줄에는 각각 $m+1$개의 정수 $b_{i, 1}, b_{i, 2}, \dots, b_{i, m+1}$ ($1 \leq b_{i, j} \leq 10^9$)이 공백으로 구분되어 주어진다.

$nm$은 짝수이며, 모든 테스트 케이스의 $nm$ 합은 $10^4$를 넘지 않는다.

각 테스트 케이스마다 최소 비용을 정수 하나로 출력한다. 조건을 만족하는 구성이 없으면 -1을 출력한다.