У KAIST заканчивается бюджет — им нужны деньги! Они посчитали, что общежития слишком роскошны по сравнению с другими зданиями KAIST; они планируют продать все здания общежитий и построить новое, совершенно неэстетичное.

Новое общежитие будет иметь форму сетки — скучнее не придумаешь — размером $N \times M$, где каждая ячейка является комнатой, в которой живут студенты. Мы собираемся добавить несколько окон, потому что хотим, чтобы студенты получали немного солнечного света в дневное время!

Мы планируем разместить ровно $w_{i,j}$ окон в комнате $(i, j)$. Каждая комната окружена 4 единичными ребрами сетки. Окно может быть построено на стороне единичного ребра сетки, и на каждой стороне единичного ребра может быть построено не более одного окна — таким образом, в каждой ячейке от 0 до 4 окон. Окно является односторонним: окно на противоположной стороне единичного ребра не считается окном в данной комнате.

К сожалению, студенты будут испытывать огромный дискомфорт, когда за их личным пространством наблюдает кто-то другой через окно. Общий дискомфорт — это количество пар студентов $\{a, b\}$ таких, что $a$ и $b$ могут видеть личное пространство друг друга через окно.

Иными словами, если единичное ребро имеет окна с обеих сторон, общий дискомфорт увеличивается на произведение количества людей, живущих в двух комнатах, разделенных этим ребром.

Вам даны $w_{i,j}$, количество окон, запланированных для комнаты $(i, j)$, и $p_{i,j}$, количество людей, живущих в комнате $(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