Problem Background

Mirko has taken up the role of a postman in a small mountain town, which can be represented as an $n \times n$ matrix. Each area has one of three states: denoted by $\texttt{K}$ for a house, $\texttt{P}$ for a post office, or $\texttt{.}$ for a pasture. Additionally, each area is assigned a height.

Every morning, Mirko delivers mail to every household in the town. He starts from the area marked with $\texttt{P}$. Mirko can only move horizontally, vertically, or diagonally to adjacent areas. Once he has delivered the last piece of mail, he must return to the post office.

Mirko is unsure how tedious his job will be. His fatigue is defined as the difference between the highest and lowest heights he reaches while delivering mail. Help him find the method with the minimum fatigue to deliver all the mail.

Problem Description

Given an $n \times n$ matrix.

Each position can be in one of three states: $\texttt{K}$, $\texttt{P}$, or $\texttt{.}$, and also has a height $h_{i,j}$.

You need to start from the position marked with $\texttt{P}$, move horizontally, vertically, or diagonally, pass through all positions marked with $\texttt{K}$, and finally return to the starting point.

During this journey, you need to minimize the difference between the maximum and minimum heights of the areas you pass through.

Please calculate the minimized value.

Input Format

The first line contains an integer $n$.

The next $n$ lines, each containing $n$ characters, represent the matrix.

The following $n$ lines, each containing $n$ positive integers, represent the heights of the areas.

Output Format

A non-negative integer representing the minimum fatigue.

Sample Input and Output

Sample Input #1

2
P.
.K
2 1
3 2

Sample Output #1

0

Sample Input #2

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

Sample Output #2

2

Sample Input #3

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

Sample Output #3

5

Notes

Sample 1 Explanation

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

Data Size and Constraints

For the matrix, $\texttt{P}$ will appear exactly once, and $\texttt{K}$ will appear at least once.

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

Source

Translated from COCI2010-2011 CONTEST #7 T4 POSTMAN

见题面 Input 部分

见题面 Output 部分