Minimizing Elevation Range Path

You are given an \(n \times n\) grid. Each cell is characterized by a state and an altitude \(h_{i,j}\). The state in each cell can be one of three characters: K, P, or ..

You must start from the cell with state P, then move in any of the 8 possible directions (horizontal, vertical, or diagonal) to traverse the grid. Your task is to visit every cell with state K at least once and finally return to the starting cell. During the route, you want to minimize the difference between the maximum and minimum altitudes encountered, i.e. minimize \(\text{max}_h - \text{min}_h\).

Output the minimum possible value of \(\text{max}_h - \text{min}_h\) that can be achieved.

inputFormat

The first line contains an integer \(n\) representing the dimension of the grid.

The next \(n\) lines each contain a string of length \(n\), representing the state of each cell. Each character is either K, P, or ..

Then, there are \(n\) lines following, each containing \(n\) space-separated integers, representing the altitude \(h_{i,j}\) of each cell.

outputFormat

Output a single integer, the minimized difference \(\text{max}_h - \text{min}_h\) over the route that satisfies the conditions.

sample

3
P.K
.K.
..K
1 2 3
4 5 6
7 8 9

8