Пес Патрон

Limits: 4 sec., 512 MiB

Важкі будні пса Патрона... От і сьогодні йому потрібно розмінувати ціле поле! Крім того, скрізь ці журналісти... Ех, слава, слава.

Поле можна уявити як прямокутну сітку розміру $n$ на $m$, де клітинки позначені «.», якщо вони порожні, або містять певну букву — якщо там щось знаходиться. Так, якщо у якійсь клітинці знаходиться міна, то вона позначена буквою $M$, якщо журналіст — буквою J, і нарешті якщо сам пес Патрон — буквою $P$.

Ні міни, ні журналісти (на диво) не рухаються, проте Патрон бігає по полю мов несамовитий — стільки ж роботи потрібно зробити! Виявляється, що спочатку на полі однакова кількість мін та журналістів, тому пес Патрон придумав такий план — після кожного успішного розмінування він даватиме інтерв’ю якомусь із журналістів. Після цього журналіст покине поле, а Патрон продовжить свою нелегку працю.

Згідно з правилами безпеки, пес Патрон може переміщатися лише між сусідніми по стороні клітинками. На одну таку дію він завжди витрачає рівно одну хвилину. Як і личить справжньому професіоналу своєї справи, і розміновує, і дає інтерв’ю Патрон миттєво.

За яким мінімальний час пес Патрон зможе розмінувати все поле та дати інтерв’ю всім журналістам?

Зауважте, що Патрон може перебігати через клітинку з журналістом, проте не давати йому інтерв’ю. Аналогічно, зважаючи на свої розміри, він також може перебігати через ще не розміновану клітинку (проте людям це робити суворо заборонено!).

Input

У першому рядку через пробіл задано три цілі числа $n$, $m$ та $k$ — розміри поля та кількість мін на ньому відповідно.

У наступних $n$ рядках задано опис поля.

Output

Виведіть єдине ціле число — мінімальну кількість часу, яка потрібна Патрону аби знешкодити всі міни та дати інтерв’ю всім журналістам.

Constraints

$1 \le n, m \le 1000$,

$1 \le k \le 10$,

у полі рівно один символ $P$, а також рівно по $k$ символів $M$ та $J$,

5 балів: $k \le 3$,

5 балів: $k \le 5$,

5 балів: $k \le 7$,

10 балів: без додаткових обмежень.

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

У першому тесті поле має розмір $3$ на $2$ та містить дві міни та двох журналістів. Оптимальний шлях Патрона виглядає так: спочатку біжить і знешкоджує міну в першому рядку (зробить це через дві хвилин від початку операції), потім нашвидкуруч дає інтерв’ю злощасному журналісту у першому рядку (3 хвилини від початку), тоді біжить та знешкоджує міну у третьому рядку (5 хвилин від початку), і врешті-решт закінчує операцію розповіддю про все це журналісту у другому стовпці третього рядка. Загалом витрачено 6 хвилин дорогоцінного часу Патрона!

У другому тесті оптимальний шлях Патрона складається з розмінування у другому стовпці, інтерв’ю у третьому, розмінування у п’ятому, та інтерв’ю у четвертому.