집배원 한상덕

한상덕은 언덕 위 마을의 우체국에서 일하게 되었다. 마을은 N x N 격자로 표현된다. 각 칸은 우체국 P, 집 K, 목초지 . 중 하나이며, 각 칸의 고도도 주어진다.

상덕이는 매일 아침 하나뿐인 우체국 P에서 출발해 모든 집에 우편을 배달해야 한다. 그는 현재 칸에서 가로, 세로, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달한 뒤에는 다시 우체국으로 돌아와야 한다.

배달 중 방문한 칸들의 고도 중 가장 높은 값과 가장 낮은 값의 차이를 피로도라고 하자. 모든 집에 배달하고 우체국으로 돌아올 수 있을 때 가능한 피로도의 최솟값을 구하라.

첫째 줄에 N이 주어진다. (2 <= N <= 50)

다음 N개 줄에는 마을을 나타내는 길이 N의 문자열이 주어진다. P는 정확히 한 번 나오며, K는 적어도 한 번 나온다.

다음 N개 줄에는 각 칸의 고도가 N x N 형태로 주어진다. 모든 고도는 1,000,000 이하의 자연수이다.

첫째 줄에 가능한 최소 피로도를 출력한다.