Во кафеаната “СИМ” има повеќе маси, но и повеќе посетители кои сакаат да седнат на истите. Поради КОВИД-19, на една маса може да седи само еден посетител. Притоа, кафеаната може да се престави како правоаголна матрица со R редови и C колони, а посетителите можат да се движат само хоризонтално и вертикално со брзина од едно квадратче во секунда. На пример, кафеаната може да изгледа вака (посетителите се означени со P, масите со M, а препреките со #):

...... .####. P...#. ...M#. .#.P.M

Во овој случај, посетителот од последниот ред е на растојание 1 од масата над него, и на растојание 2 од масата десно од него. Доколку тој отиде до најблиската маса, другиот посетител треба да направи многу голем напор за да стигне до масата која што е доле-десно. Но, доколку посетителот од последниот ред се одлучи да отиде до масата која што е десно од него за време од 2 секунди, тогаш другиот посетител може да стигне до маса за 4 секунди. На овој начин, за 4 секунди и двајцата може да имаат маса.

Напишете програма која за даден изглед на кафеана, како се наредени посетителите и масите во неа, ќе пресметува за колку најмалку време може сите посетители да најдат своја маса (доколку истите соработуваат меѓусебно/оптимално како во примерот даден погоре). Притоа, можете да претпоставите дека масите и посетителите се многу мали во однос на самите квадратчиња од матрицата (кои ја претставуваат кафеаната), па повеќе посетители (при движење низ кафеаната) може да се наоѓаат во исто квадратче во даден момент, како и да поминуваат низ квадратчиња на кои што има маси. Секако, не може да се поминува низ квадратчиња кои што претставуваат препреки.

Влез

Во првиот ред се запишани два цели броја R и C (2 <= R, C <= 50), кои го означуваат бројот на редови и колони соодветно. Во секој од следните R редови се запишани по C знаци ‘P’ (посетител), ‘M’ (маса), ‘.’ (празно место) или ‘#’ (препрека), кои го означуваат изгледот на кафеаната, посетителите и масите.

Во сите тест случаи, бројот на маси ќе биде поголем или еднаков на бројот на посетители, и нема да постојат случаи со повеќе од 100 маси или повеќе од 100 посетители.

Забелешка: Во тест случаи кои носат најмалку 20% од поените, ќе има само еден посетител во кафеаната. Во други тест случаи кои носат најмалку 30% од поените, ќе важи R, C <= 5.

Излез

Во еден ред се запишува бараното најмало време. Секој посетител мора да седне на различна маса. Тест случаите ќе бидат направени така што секогаш ќе постои решение.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5 6
......
.####.
P...#.
...M#.
.#.P.M

излез
4