Postman Han Sangdeok

Han Sangdeok works at a post office in a village on a hill. The village is represented as an N x N grid. Each cell is one of a post office P, a house K, or a pasture ., and the altitude of every cell is also given.

Every morning, Sangdeok starts from the only post office P and must deliver mail to every house. From his current cell, he may move to any horizontally, vertically, or diagonally adjacent cell. After delivering the last letter, he must return to the post office.

Define the fatigue of a delivery route as the difference between the highest and lowest altitudes among all cells visited during the route. Find the minimum possible fatigue that lets him deliver to all houses and return to the post office.

The first line contains N. (2 <= N <= 50)

The next N lines contain strings of length N describing the village. P appears exactly once, and K appears at least once.

The following N lines contain the altitudes of the cells in N x N form. Every altitude is a natural number not greater than 1,000,000.

Output the minimum possible fatigue on the first line.