Mirko has got a mailman job in a small town in the hills. The town can be represented by an \(N \times 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 the 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.

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 \le N \le 50\)).

The following \(N\) lines represent the 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.

riseoj 작성

출처 COCI 2010/2011 Contest 7