KAIST 的預算快用完了——他們需要錢！他們認為宿舍與 KAIST 的其他建築相比太過奢華；他們計畫賣掉所有的宿舍建築，並建造一個全新的、完全不講究美感的宿舍。

新的宿舍將呈現網格狀——沒有比這更無聊的設計了——大小為 $N \times M$，每個格子都是學生居住的房間。我們打算增加一些窗戶，因為我們希望學生在白天能享受到陽光！

我們計畫在房間 $(i, j)$ 中設置恰好 $w_{i,j}$ 個窗戶。每個房間都被網格的 4 條單位邊所包圍。窗戶可以建在網格的單位邊上，且每條單位邊的一側最多只能建一個窗戶——因此每個房間有 0 到 4 個窗戶。窗戶是單向的：單位邊另一側的窗戶不計入該房間的窗戶數量。

不幸的是，當學生的私人空間被其他人透過窗戶窺視時，他們會感到極大的不適。總不適感定義為所有學生對 $\{a, b\}$ 的數量，使得 $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