一个小镇被分成N * N的相邻格子，每个格子都用一个字母来描述。‘K’表示房子，‘P’表示邮局, ‘.’表示草地.，另外每个格子都有一个海拔高度（他可以走水平、竖直、对角线的相邻格子）。一个邮递员每天从邮局出发（只有一个邮局）为每个房子（至少有一个房子）送一封信后回到邮局。他工作的烦恼度用他走过的地方的最大海拔和最小海拔之差来描述。现给定以上参数，求出他的最小烦恼度。
INPUT
第一行一个数N (2 ≤ N ≤ 50).
接下来N行，每行N个字母。
再下来N行，每行N个数字，表示海拔高度。高度小于1 000 000.
OUTPUT
一个数表示最小烦恼度。
SAMPLE TESTS
input
2
P.
.K
2 1
3 2
output
0

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

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