题目背景

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

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

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

题目描述

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

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

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

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

请你求出最小化的值。

输入格式

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

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

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

输出格式

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

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

提示

样例 1 解释

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

数据规模及约定

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

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

说明

本题满分 $100$ 分。

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