Hiking

Alice likes to hike. She likes some stretches of track and dislikes others, so the cost of walking a stretch records how she feels about it. Given a map with the cost of going from one cell to the next, find the average cost of a hike in that area.

The map is a rectangular grid of cells. Each cell carries the cost of taking one step from it to each of its northern, western, southern and eastern neighbours. A hike is a finite sequence of steps, each of which goes from a cell to one of its neighbours. The cost of a hike is the sum of the costs of its steps. A cost can be negative.

Once the start cell and the end cell are fixed, Alice always chooses a hike of minimum cost. Compute the average of those minimum costs over every ordered pair of distinct start and end cells. The start cell and the end cell must differ. A cost depends on the direction of travel, so $(a, b)$ and $(b, a)$ are different ordered pairs and each counts once. If several minimum-cost hikes join the same two cells, that pair still counts only once. The average therefore runs over exactly $wh(wh-1)$ ordered pairs.

The first line contains the width $w$ and the height $h$ of the map ($2 \le w, h \le 50$). Rows are numbered $1$ to $h$ from the top and columns $1$ to $w$ from the left.

Each of the next $h$ lines contains $w$ integers. The $j$-th integer on the $i$-th of those lines is the cost of one step from cell $(i, j)$ to its northern neighbour $(i-1, j)$, and it is between $-10^7$ and $10^7$.

Three more blocks of $h$ lines each follow, in the same format. They give the cost of a step to the western neighbour $(i, j-1)$, then to the southern neighbour $(i+1, j)$, then to the eastern neighbour $(i, j+1)$.

Walking off the map is not allowed, and the corresponding entries are $0$.

A minimum-cost hike exists between any two cells, so no sequence of steps returns to its starting cell with a negative total cost.

Print on one line the smallest integer that is greater than or equal to the average cost of the minimum-cost hikes over all ordered pairs of distinct start and end cells.