题目背景

面条老师 在一个山中小镇里得到了一个邮递员的差事。这个小镇可以用一个 $n \times n$ 的矩阵表示。每个区域有三种状态：用 $\texttt{K}$ 表示房屋，用 $\texttt{P}$ 表示邮局或用 $\texttt{.}$ 表示牧场。此外，每个区域被分配一个高度。

每天早晨，面条老师 都给镇上的每户人家送邮件。他从用 $\texttt{P}$ 表示的区域开始。面条老师 只能水平、垂直或斜向移动到相邻的区域。他一旦送完最后一封邮件，就必须返回邮局。

面条老师 不知道他的工作会有多无聊。令 面条老师 在投递邮件时所到的最高处和最低处的高度之差等于他的疲劳度。帮他找出疲劳度最小的方式，让 面条老师 投递所有的邮件。

题目描述

给定一个 $n \times n$ 的矩阵。

每个位置可能有 $\texttt{K}$ $\texttt{P}$ $\texttt{.}$ 三种可能状态，此外还有一个高度 $h_{i,j}$。

你需要从状态为 $\texttt{P}$ 的位置开始，水平、垂直或斜向移动，经过所有状态为 $\texttt{K}$ 的位置，最终回到起点。

在这路程中，你需要让经过的位置的 $max_h-min_h$ 最小化。

请你求出最小化的值。

输入格式

第一行包含一个整数 $n$。

下面的 $n$ 行每行 $n$ 个字符表示矩阵。

下面的 $n$ 行每行 $n$ 个正整数，表示区域高度。

输出格式

一个非负整数表示最小疲劳度。

样例 #1

样例输入 #1

2
P.
.K
2 1
3 2

样例输出 #1

0

样例 #2

样例输入 #2

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

样例输出 #2

2

样例 #3

样例输入 #3

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

样例输出 #3

5

提示

样例 1 解释

从邮局开始，面条老师 可以直接移动到房屋，然后再回到邮局。因为这两个区域高度相同，所以 面条老师的疲劳等于 $0$。

数据规模及约定

对于矩阵，其中 $\texttt{P}$ 将正好出现一次，而 $\texttt{K}$ 将至少出现一次。

对于 $100\%$ 的数据 $2 \le n \le 50$

说明

本题满分 $100$ 分。

注意看时间限制！！！！！！！！！！！！！！！！！！