문제

Author: Goran Gašić

Mirko has got a mailman job in a small town in the hills. The town can be represented by a N×N matrix. Each field contains one of the following, exclusively: a house denoted by ‘K’, the post office denoted by ‘P’, or a pasture denoted by ‘.’. Additionally, each field is assigned an altitude. Every morning, Mirko delivers mail to all houses in the town. He starts at the field denoted by ‘P’, which represents a single post office in the town. Mirko is allowed to move horizontally, vertically and diagonally, to adjacent squares only. Once he delivers the last piece of mail, he must return to the post office. Mirko did not have a clue about how tiresome his job will be. Let the difference between the heights of the highest and the lowest field Mirko visits while delivering the mail be equal to his tiredness. Help him out and determine the least tiredness possible for Mirko to deliver all the mail.

입력

The first line of input contains an integer N (2 ≤ N ≤ 50). The following N lines represent fields in the corresponding matrix row. The character ‘P’ will appear exactly once, while the character ‘K’ will appear at least once. The following N lines each contain N positive integers, the altitudes of the fields in the corresponding matrix row. Those values are less than 1 000 000.

출력

In a single line of output print a single integer that represents the minimum possible tiredness.

예제 입력 1

2
P.
.K
2 1
3 2

예제 출력 1

0

예제 입력 2

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

예제 출력 2

2

예제 입력 3

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

예제 출력 3

5