Background

Mirko got a job as a postman in a small mountain town. The town can be represented as an $n \times n$ matrix. Each cell has one of three types: a house marked with K, a post office marked with P, or a pasture marked with .. In addition, each cell is assigned a height.

Every morning, Mirko delivers mail to every house in the town. He starts from the cell marked P. Mirko can move to an adjacent cell horizontally, vertically, or diagonally. After delivering the last letter, he must return to the post office.

Mirko does not know how boring his job will be. Let Mirko’s fatigue be the difference between the maximum and minimum heights among all cells he visits while delivering the mail. Help him find a way to deliver all the mail with the minimum possible fatigue.

Problem Description

You are given an $n \times n$ matrix.

Each position may be one of K, P, .. It also has a height $h_{i,j}$.

You need to start from the position marked P, move horizontally, vertically, or diagonally, visit all positions marked K, and finally return to the starting position.

Along this route, you need to minimize $max_h - min_h$ over all visited positions.

Output this minimum value.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain $n$ characters describing the matrix.

The next $n$ lines each contain $n$ positive integers, representing the heights of the cells.

Output Format

Output a non-negative integer, the minimum fatigue.

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

Explanation of Sample 1

Starting from the post office, Mirko can move directly to the house and then return to the post office. Since the two cells have the same height, Mirko’s fatigue is $0$.

Constraints

In the matrix, P appears exactly once, and K appears at least once.

For $100\%$ of the testdata, $2 \le n \le 50$.

Notes

This problem is worth $100$ points.

Translated from COCI2010-2011 CONTEST #7 T4 POŠTAR.

Translated by ChatGPT 5