Description

You are given an $n \times n$ matrix.

Each position may be one of K, P, .. It also has a height $h_{i,j}$.

You need to start from the position marked P, move horizontally, vertically, or diagonally, visit all positions marked K, and finally return to the starting position.

Along this route, you need to minimize $max_h - min_h$ over all visited positions.

Output this minimum value.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain $n$ characters describing the matrix.

The next $n$ lines each contain $n$ positive integers, representing the heights of the cells.

Output Format

Output a non-negative integer, the minimum fatigue.

2
P.
.K
2 1
3 2

0

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

2

3
K.P
...
K.K
3 3 4
9 5 9
8 3 7

5

Hint

Explanation of Sample 1

Starting from the post office, Mirko can move directly to the house and then return to the post office. Since the two cells have the same height, Mirko’s fatigue is $0$.

Constraints

In the matrix, P appears exactly once, and K appears at least once.

For $100\%$ of the testdata, $2 \le n \le 50$.

Notes

This problem is worth $100$ points.

Translated from COCI2010-2011 CONTEST #7 T4 POŠTAR.

Translated by ChatGPT 5