暂无测试数据。

Description

森林王国的中央游乐园里，有一个 \(n \cdot n\) 的矩阵形式的梅花桩。每个梅花桩都有自己的高度 \(h\)，有些梅花桩上有松鼠最喜欢吃的松果。现在松鼠 \(\text{Scarral}\) 目前站在其中一根梅花桩上，它想吃掉所有的松果，\(\text{Scarral}\) 能从当前所在位置向它周围 \(8\) 个相邻的位置跳跃，如果我们定义郁闷值为 \(\text{Scarral}\) 在吃松果过程中所经过的最高处和最低处高度之差，那么\(\text{Scarral}\)的郁闷值最低是多少。

---

Input

输入分为 \(3\) 个部分

第 \(1\) 行是一个整数 \(n\)，表示 \(n\cdot n\) 矩阵。

接下来是一个 \(n\cdot n\) 的矩阵，每个位置可能是 K、P 或者 .。K 表示这棵梅花桩上有松果，P 表示松鼠开始的位置，. 表示这个梅花桩上没有松果。

接下来又是一个 \(n\cdot n\) 的矩阵，每个位置表示该位置上梅花桩的高度。

---

Output

输出一行一个整数，表示最小的郁闷值。

---

Sample

Sample input

#1

2
P.
.K
2 1
3 2

#2

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

#3

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

Sample output

#1

0

#2

2

#3

5

---

Hint

注意：至少会有一个松果。

对于 \(30\%\) 的数据 \(n\le 10,\ h\le 100\)；

对于 \(60\%\) 的数据 \(n\le 50,\ h\le 100\)；

对于 \(100\%\) 的数据 \(1\le n\le 50,\ 1<h\le 1000\)。