Dog Patron

Limits: 4 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Hard weekdays of dog Patron... Today he needs to demine a whole field! Besides, these journalists are everywhere... Ah, fame, fame.

Logan’s field can be represented as a rectangular grid of size \(n\) by \(m\), where cells are marked with "." if they are empty, or contain a certain letter if something is there. Thus, if a mine is located in some cell, it is marked with the letter \(M\), if a journalist — with the letter \(J\), and finally if dog Patron himself — with the letter \(P\).

Neither mines nor journalists (surprisingly) move, but Patron runs across the field like crazy — so much work needs to be done! It turns out that initially there is an equal number of mines and journalists on the field, so dog Patron came up with the following plan — after each successful demining, he will give an interview to one of the journalists. After that, the journalist will leave the field, and Patron will continue his hard work.

According to safety rules, dog Patron can only move between side-adjacent cells. For one such action, he always spends exactly one minute. As befits a true professional of his craft, Patron both demines and gives interviews instantly.

What is the minimum time in which dog Patron will be able to demine the entire field and give interviews to all journalists?

Note that Patron can run through a cell with a journalist, but not give him an interview. Similarly, given his size, he can also run through an uncleared mine cell (however, people are strictly forbidden to do this!).

Input

The first line contains three integers \(n\), \(m\), and \(k\) separated by a space — the sizes of the field and the number of mines on it, respectively.

The next \(n\) lines give the description of the field.

Output

Print a single integer — the minimum amount of time Patron needs to neutralize all mines and give interviews to all journalists.

Constraints

\(1 \le n, m \le 1000\),

\(1 \le k \le 10\),

there is exactly one character \(P\) in the field, as well as exactly \(k\) characters of \(M\) and \(J\) each,

5 points: \(k \le 3\),

5 points: \(k \le 5\),

5 points: \(k \le 7\),

10 points: without additional constraints.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 3 2 .MJ P.. .JM	6

Input (stdin) сopy	Output (stdout) сopy
1 5 2 PMJJM	5

Notes

In the first test, the field is of size \(3\) by \(2\) and contains two mines and two journalists. Patron’s optimal path looks like this: first he runs and neutralizes the mine in the first row (he will do this two minutes from the start of the operation), then he quickly gives an interview to the ill-fated journalist in the first row (3 minutes from the start), then he runs and neutralizes the mine in the third row (5 minutes from the start), and finally ends the operation by telling everything about it to the journalist in the second column of the third row. A total of 6 minutes of Patron’s precious time was spent!

In the second test, Patron’s optimal path consists of demining in the second column, interviewing in the third, demining in the fifth, and interviewing in the fourth.