Tube Master II

유우카는 "Tube Master"를 하고 있다. 게임 판은 $n \times m$개의 칸과 $(n + 1) \times (m + 1)$개의 교차점으로 나뉘어 있다. 교차점은 $(n + 1) \times m$개의 가로 튜브와 $n \times (m + 1)$개의 세로 튜브로 이어져 있다. 칸은 $1 \leq i \leq n$, $1 \leq j \leq m$을 만족하는 $(i, j)$로 표시하고, 교차점은 $1 \leq i \leq (n+1)$, $1 \leq j \leq (m+1)$을 만족하는 $(i, j)$로 표시한다. 각 칸 $(i, j)$에는 정수 $\mathit{count}\_{i, j}$가 적혀 있다.

유우카는 다음 제약을 지키며 일부 튜브를 사용하려고 한다.

1. 각 교차점에 연결된 튜브 중 사용하는 튜브는 0개 또는 2개이다.
2. 연속한 가로 튜브는 동시에 사용할 수 없고, 연속한 세로 튜브도 동시에 사용할 수 없다. 두 튜브는 같은 교차점을 공유할 때에만 연속한다.
3. 칸 $(i, j)$를 둘러싼 튜브 중 정확히 $\mathit{count}\_{i, j}$개를 사용한다.

교차점 $(i, j)$와 $(i, j + 1)$을 잇는 튜브를 사용하면 비용 $a\_{i, j}$가 든다. 교차점 $(i, j)$와 $(i + 1, j)$를 잇는 튜브를 사용하면 비용 $b\_{i, j}$가 든다. 제약을 만족하는 배치 중 총비용이 가장 작은 값을 구한다.

입력에는 0개 이상의 테스트 케이스가 들어 있으며, 파일의 끝에서 입력이 끝난다. 각 테스트 케이스는 다음과 같다.

첫 줄에 두 정수 $n$과 $m$ ($1 \leq n, m \leq 100$)이 주어진다.

이어지는 $n$개의 줄 중 $i$번째 줄에는 정수 $\mathit{count}\_{i, 1}, \mathit{count}\_{i, 2}, \dots, \mathit{count}\_{i, m}$ ($0 \leq \mathit{count}\_{i, j} \leq 4$)이 $m$개 주어진다.

이어지는 $(n + 1)$개의 줄 중 $i$번째 줄에는 정수 $a\_{i, 1}, a\_{i, 2}, \dots, a\_{i, m}$이 $m$개 주어진다.

마지막 $n$개의 줄 중 $i$번째 줄에는 정수 $b\_{i, 1}, b\_{i, 2}, \dots, b\_{i, m + 1}$이 $(m + 1)$개 주어진다.

제약은 $1 \leq a\_{i, j}, b\_{i, j} \leq 10^9$이다. 모든 테스트 케이스에 걸친 $n \cdot m$의 합은 $10^4$을 넘지 않는다.

각 테스트 케이스에 대해 유효한 배치의 최소 비용을 출력한다. 유효한 배치가 없으면 "-1"을 출력한다.