KAIST est à court de budget — ils ont besoin d'argent ! Ils ont pensé que les dortoirs étaient bien trop luxueux par rapport aux autres bâtiments de KAIST ; ils ont prévu de vendre tous les bâtiments des dortoirs et d'en construire un nouveau, totalement inesthétique.

Le nouveau dortoir aura une forme de grille — on ne peut pas faire plus ennuyeux — de taille $N \times M$, chaque cellule étant une chambre où vivent les étudiants. Nous allons ajouter quelques fenêtres, car nous voulons que les étudiants profitent de la lumière du soleil pendant la journée !

Nous prévoyons d'avoir exactement $w_{i,j}$ fenêtres dans la chambre $(i, j)$. Chaque chambre est entourée de 4 arêtes unitaires de la grille. Une fenêtre peut être construite sur le côté d'une arête unitaire de la grille, et au plus une fenêtre peut être construite de chaque côté d'une arête unitaire — ainsi, chaque cellule possède entre 0 et 4 fenêtres. Une fenêtre est unidirectionnelle : une fenêtre située sur le côté opposé d'une arête unitaire ne compte pas comme une fenêtre pour la chambre.

Malheureusement, les étudiants ressentiront un grand inconfort lorsque leur espace privé sera observé par quelqu'un d'autre à travers la fenêtre. L'inconfort total est le nombre de paires d'étudiants $\{a, b\}$ telles que $a$ et $b$ peuvent voir l'espace privé de l'autre à travers la fenêtre.

En d'autres termes, si une arête unitaire possède des fenêtres des deux côtés, l'inconfort total augmente du produit du nombre de personnes vivant dans les deux chambres partageant cette fenêtre.

On vous donne $w_{i,j}$, le nombre de fenêtres prévues pour la chambre $(i, j)$, et $p_{i,j}$, le nombre de personnes vivant dans la chambre $(i, j)$. Votre tâche est de trouver l'inconfort total minimum qui peut être atteint en disposant les fenêtres correctement.

Entrée

La première ligne contient deux entiers $N$ et $M$ : les dimensions de la grille. Chacune des $N$ lignes suivantes contient $M$ entiers séparés par des espaces $p_{i,j}$. Chacune des $N$ lignes suivantes contient $M$ entiers séparés par des espaces $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$)

Sortie

Affichez un seul entier : l'inconfort total minimum.

Exemples

Entrée 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

Sortie 1

178

Entrée 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

Sortie 2

0