KAIST kończy się budżet — potrzebują pieniędzy! Uznali, że akademiki są zbyt luksusowe w porównaniu z innymi budynkami KAIST; zaplanowali sprzedaż wszystkich budynków akademików i budowę nowego, całkowicie nieestetycznego obiektu.

Nowy akademik będzie miał kształt siatki o wymiarach $N \times M$ — nie może być nic bardziej nudnego — gdzie każda komórka jest pokojem, w którym mieszkają studenci. Zamierzamy dodać kilka okien, ponieważ chcemy, aby studenci mieli dostęp do światła słonecznego w ciągu dnia!

Planujemy umieścić dokładnie $w_{i,j}$ okien w pokoju $(i, j)$. Każdy pokój jest otoczony przez 4 krawędzie jednostkowe siatki. Okno może zostać zbudowane na boku krawędzi jednostkowej siatki i na każdym boku krawędzi jednostkowej może znajdować się co najwyżej jedno okno — dzięki temu każdy pokój ma od 0 do 4 okien. Okno jest jednostronne: okno po przeciwnej stronie krawędzi jednostkowej nie liczy się jako okno w danym pokoju.

Niestety, studenci odczują ogromny dyskomfort, gdy ich prywatna przestrzeń będzie obserwowana przez kogoś innego przez okno. Całkowity dyskomfort to liczba par studentów $\{a, b\}$ takich, że $a$ i $b$ mogą widzieć swoją prywatną przestrzeń przez okno.

Innymi słowy, jeśli krawędź jednostkowa ma okna po obu stronach, całkowity dyskomfort wzrasta o iloczyn liczby osób mieszkających w dwóch pokojach dzielących to okno.

Dane są $w_{i,j}$, liczba okien zaplanowanych dla pokoju $(i, j)$, oraz $p_{i,j}$, liczba osób mieszkających w pokoju $(i, j)$. Twoim zadaniem jest znalezienie minimalnego całkowitego dyskomfortu, jaki można osiągnąć poprzez odpowiednie rozmieszczenie okien.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $N$ i $M$: wymiary siatki. Każda z następnych $N$ linii zawiera $M$ liczb całkowitych $p_{i,j}$ oddzielonych spacjami. Każda z następnych $N$ linii zawiera $M$ liczb całkowitych $w_{i,j}$ oddzielonych spacjami.

• $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$)

Wyjście

Wypisz jedną liczbę całkowitą: minimalny całkowity dyskomfort.

Przykład

Wejście 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

Wyjście 1

178

Wejście 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

Wyjście 2

0