Пес Патрон

Обмеження: 4 сек., 512 МіБ

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

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

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Обмеження

\(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 балів: без додаткових обмежень.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 3 2 .MJ P.. .JM	6

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 5 2 PMJJM	5

Примітки

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

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