KAIST는 예산이 부족하여 돈이 필요합니다! 그들은 기숙사가 KAIST의 다른 건물들에 비해 너무 호화롭다고 생각하여, 모든 기숙사 건물을 팔고 완전히 미적 감각이 없는 새로운 건물을 짓기로 계획했습니다.

새 기숙사는 $N \times M$ 크기의 격자 모양이 될 것입니다. 각 칸은 학생들이 거주하는 방입니다. 낮 동안 학생들이 햇빛을 받을 수 있도록 창문을 추가하려고 합니다!

우리는 방 $(i, j)$에 정확히 $w_{i,j}$개의 창문을 설치할 계획입니다. 각 방은 격자의 4개의 단위 변으로 둘러싸여 있습니다. 창문은 격자의 단위 변 한쪽에 설치할 수 있으며, 각 단위 변의 한쪽 면에는 최대 하나의 창문만 설치할 수 있습니다. 따라서 각 칸은 0개에서 4개의 창문을 가집니다. 창문은 단방향입니다. 단위 변의 반대편에 있는 창문은 해당 방의 창문으로 간주하지 않습니다.

불행히도, 학생들은 창문을 통해 누군가 자신의 사적인 공간을 들여다볼 때 큰 불편함을 느낍니다. 총 불편함은 창문을 통해 서로의 사적인 공간을 볼 수 있는 학생 쌍 $\{a, b\}$의 수입니다.

즉, 단위 변의 양쪽 모두에 창문이 있다면, 총 불편함은 해당 창문을 공유하는 두 방에 거주하는 사람 수의 곱만큼 증가합니다.

방 $(i, j)$에 계획된 창문의 수 $w_{i,j}$와 방 $(i, j)$에 거주하는 사람의 수 $p_{i,j}$가 주어집니다. 창문을 적절히 배치하여 얻을 수 있는 최소 총 불편함을 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에는 격자의 크기를 나타내는 두 정수 $N$과 $M$이 주어집니다. 다음 $N$개의 줄에는 각각 $M$개의 정수 $p_{i,j}$가 주어집니다. 다음 $N$개의 줄에는 각각 $M$개의 정수 $w_{i,j}$가 주어집니다.

• $1 \le N \le 50$
• $1 \le M \le 50$
• $1 \le p_{i,j} \le 1000$ ($1 \le i \le N, 1 \le j \le M$)
• $0 \le w_{i,j} \le 4$ ($1 \le i \le N, 1 \le j \le M$)

출력

최소 총 불편함을 나타내는 정수 하나를 출력합니다.

예제

입력 1

4 3
1 7 10
7 2 8
7 9 10
4 6 4
3 3 3
3 2 4
4 3 4
2 2 3

출력 1

178

입력 2

4 3
2 2 9
9 8 4
8 4 5
7 5 2
0 1 0
1 0 1
0 0 1
0 1 0

출력 2

0