At UMT University, where technological ideas are always nurtured with passion and creativity, two outstanding members of the Computer Science Club An, a talented student, and Tiến, her brilliant friend, embarked on a new journey. During a practical simulation competition organized by the Faculty of Information Technology, they decided to collaborate on a project called "Cross the High Mountain."

The story unfolds in a remote highland village, where delivering mail isn't just a matter of moving between points, it's a challenge against the rugged terrain. An designed the village as a square matrix of size ~N × N~, where each cell represents an area with a specific altitude. Some cells are empty grassland ".", some are houses ~"A"~, and there is exactly one cell that represents the post office ~"T"~ the starting and ending point of the journey.

In the model An built, the mail carrier must start from the post office, visit all the houses to deliver mail, and then return to the post office. But instead of simply measuring distance like traditional models, Tiến introduced a more realistic metric: tiredness, defined as the difference between the highest and lowest altitude the carrier passes through during the entire trip. The carrier can move to adjacent cells in all 8 directions (including diagonals), but cannot traverse areas with altitudes outside a tolerable range. So, the challenge is to determine a route that visits all houses, returns to the post office, and minimizes the tiredness. This is not just an algorithmic problem, it's a challenge grounded in both realism and compassion. Now, An and Tiến are counting on you, their companion at UMT, to help solve this meaningful programming puzzle!

Input

The first line contains an integer ~N(2 ≤ N ≤ 50)~.

The next N lines describe the matrix representing the village. The character "T" appears exactly once (the post office), while the character "A" appears at least once (the houses).

The following N lines describe the altitude of each area in the matrix. Each altitude is a natural number not greater than 1,000,000.

Output

Print the smallest fatigue level on the first line.

Sample Input 1

3
A.T
...
A.A
3 3 4
9 5 9
8 3 7

Sample Ouput 1

5