Description

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

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

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

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

请你求出最小化的值。

Input Format

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

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

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

Output Format

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

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

样例 1 解释

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

数据规模及约定

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

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

说明

本题满分 $100$ 分。

译自 COCI2010-2011 CONTEST #7 T4 POŠTAR