25739번 - Window Arrangement 다국어

문제

KAIST is running out of budget — they need some money! They thought the dormitories were way too luxurious compared to the other buildings of KAIST; they planned to sell all the dormitory buildings and build a new completely non-aesthetic one.

The new dormitory will be of a grid-shape — it can’t be more boring than this — of size $N\times M,ドル each cell being the room for the students. We are going to add some windows, because we want students to get some sunlight during the daytime!

We plan to have exactly $w_{i,j}$ windows for the room $(i,j)$. A window can be built on the side of an edge of a grid, and at most one window can be built on each side of an edge. A window is one-sided: a window on the opposite side of an edge does not count as a window of the room.

Unfortunately, students will experience huge discomfort when their privacy is watched by someone else through the window. Total discomfort is the number of set of students $\{a,b\},ドル such that $a$ and $b$ can see each other’s privacy through the window.

Precisely, if an edge has windows on both sides, total discomfort increases by the product of the number of people living in two houses sharing the window.

You’re given $w_{i,j},ドル and $p_{i,j},ドル the number of people living in the room $(i,j)$. Your task is to find the minimum total discomfort that can be achieved by arranging the windows properly.

입력

The first line contains the size of the grid, $N$ and $M$.

Following $N$ lines contains $M$ space-separated integers $p_{i,j}$.

Following $N$ lines contains $M$ space-separated integers $w_{i,j}$.

출력

Output the minimum total discomfort.

제한

• 1ドル\le N\le 50$
• 1ドル\le M\le 50$
• 1ドル\le p_{i,j}\le 1,円 000$ (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$)

힌트