미르코는 언덕에 있는 조그만 마을에서 집배원 일을 한다. 이 마을은 NxN 행렬의 구조로 나타낼 수 있다.

각 필드는 세 가지 중의 하나로 표시된다. 집은 K 로 , 우체국은 P 로 , 나대지는 . 으로 표시되고 각 필드에는 각 필드의 고지가 표시되어 있다.

매일 아침 , 미르코 마을에 있는 모든 집에 편지를 배달한다.

우체국(P로 표시된 점이고 우체국은 마을에서 하나밖에 없다)에서 출발하여 인접한 대각선 , 수직 , 수평방향으로 움직일 수 있다. 그리고 처음 지점으로 돌아와야 한다.

미르코는 이 직업이 얼마나 지겨울지를 알지 못했었다.

그가 방문하는 필드의 최고고도와 최저고도의 차이를 지루함의 정도라고 할 때 지루함의 정도를 최소로 하는 길을 찾아서 이 차를 출력 하는 것이 문제이다.

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.

출력

입출력 예

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

출처:coci