하이킹

앨리스는 하이킹을 좋아한다. 마음에 드는 구간도 있고 싫어하는 구간도 있어서, 구간을 걷는 비용으로 그 호감도를 나타낸다. 비용이 적힌 지도가 주어질 때 그 지역에서 하이킹하는 평균 비용을 구하자.

지도는 칸으로 이루어진 직사각형 격자다. 각 칸에는 그 칸에서 북쪽, 서쪽, 남쪽, 동쪽 이웃 칸으로 한 걸음 이동하는 비용이 적혀 있다. 하이킹은 유한 개의 걸음으로 이루어진 열이고, 각 걸음은 어떤 칸에서 그 칸의 이웃 칸으로 이동한다. 하이킹의 비용은 각 걸음의 비용을 모두 더한 값이다. 비용은 음수일 수도 있다.

출발 칸과 도착 칸이 정해지면 앨리스는 항상 비용이 최소인 하이킹을 고른다. 서로 다른 출발 칸과 도착 칸의 모든 순서쌍에 대해 최소 비용 하이킹의 비용을 구하고, 그 평균을 구하자. 출발 칸과 도착 칸은 서로 달라야 한다. 이동 방향에 따라 비용이 다르므로 $(a, b)$와 $(b, a)$는 서로 다른 순서쌍이고 각각 한 번씩 센다. 두 칸 사이에 최소 비용 하이킹이 여러 개 있어도 그 순서쌍은 한 번만 센다. 그래서 평균을 낼 때 쓰는 순서쌍은 정확히 $wh(wh-1)$개다.

첫째 줄에 지도의 너비 $w$와 높이 $h$가 주어진다 ($2 \le w, h \le 50$). 행은 위에서 아래로 $1$부터 $h$까지, 열은 왼쪽에서 오른쪽으로 $1$부터 $w$까지 번호를 붙인다.

이어지는 $h$개의 줄에는 각각 $w$개의 정수가 주어진다. 그중 $i$번째 줄의 $j$번째 수는 칸 $(i, j)$에서 북쪽 이웃 $(i-1, j)$로 한 걸음 이동하는 비용이고, $-10^7$ 이상 $10^7$ 이하다.

그다음 각각 $h$개의 줄로 이루어진 블록이 세 개 더 이어진다. 형식은 첫 블록과 같고, 순서대로 서쪽 이웃 $(i, j-1)$, 남쪽 이웃 $(i+1, j)$, 동쪽 이웃 $(i, j+1)$로 이동하는 비용이다.

지도 밖으로 나가는 이동은 할 수 없고, 그런 자리의 비용은 $0$으로 주어진다.

어떤 두 칸 사이에도 최소 비용 하이킹이 존재한다. 즉 같은 칸으로 돌아오면서 비용의 합이 음수가 되는 걸음의 열은 없다.

서로 다른 출발 칸과 도착 칸의 모든 순서쌍에 대한 최소 비용 하이킹 비용의 평균보다 크거나 같은 가장 작은 정수를 한 줄에 출력한다.