== include(page="template/taskheader" task_id="dungeon2") ==

Dungeon Crawl: Paper Soup tocmai a devenit cel mai popular joc, iar tu eşti pe cale să îl încerci. Jocul se desfăşoară pe un teren dreptunghiular cu $N$ linii şi $M$ coloane, unde fiecare celulă este de unul dintre cele cinci tipuri descrise mai jos:
 
• celulă liberă *$'.'$*;
• perete *$'#'$*;
• celulă cu monedă *$'o'$*;
• celulă cu mină explozivă *$'X'$*;
• celulă de start *$'S'$*;
 
Se garantează că pe prima, respectiv ultima linie şi coloană se află pereţi (de precizat că este imposibilă deplasarea prin pereţi). Terenul poate conţine una sau mai multe celule de start. În momentul în care jocul începe, jucătorul va fi poziţionat iniţial într-una dintre celulele de start, marcate cu ‘S’. Deoarece jocul se desfăşoară într-un sistem de peşteri cu vizibilitate redusă (vezi numele jocului), jucătorul nu poate vedea toată harta, ci doar o zona de vizibilitate restrânsă, reprezentată de un pătrat de $3 × 3$ centrat în poziţia sa curentă. Mai mult, în această zonă de vizibilitate minele şi celulele de start apar drept celule libere (sunt invizibile pentru jucător).
 
La fiecare pas, jucătorul poate să se mişte pe direcţiile nord, sud, est sau vest. Dacă acesta ajunge pe o poziţie cu o monedă, colectează moneda, iar aceasta dispare de pe hartă. Dacă acesta ajunge pe o
poziţie cu mină, sistemul de peşteri se prăbuşeste, jucătorul pierde toate monezile colectate până în acel moment, iar jocul se termină.
 
Din fericire, urmărind diverse ghiduri pe internet ai aflat harta exactă a terenului, însă nu ştii în care dintre punctele de start vei fi repartizat – este garantat însă că vei porni dintr-o celulă de start. Considerând căvei adopta cea mai bună strategie, care este numărul maxim de monezi pe care îl poţi obţine garantat, indiferent de unde vei fi poziţionat la început?

Poveste şi cerinţă...

h2. Date de intrare

Pe prima linia a fişierul de intrare $dungeon2.in$ se vor găsi valorile $N$ şi $M$: dimensiunile terenului pe care se va desfăşura jocul, conform ghidurilor de pe internet. Următoarele $N$ linii conţin fiecare câte un şir de caractere de lungime $M$, reprezentând harta, conform codificării descrise în enunţ.

Fişierul de intrare $dungeon2.in$ ...

h2. Date de ieşire

În fişierul de ieşire $dungeon2.out$ se va afişa un singur număr natural, numărul maxim de monezi care se poate obţine garantat pe acel teren.

În fişierul de ieşire $dungeon2.out$ ...

h2. Restricţii

* Fie $S$ numărul de celule de start ce se află pe hartă.
* $1 ≤ S ≤ 60$
* $1 ≤ N,M ≤ 400$
* În plus:
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| 1 | 3 | $S = 1$. Nu există mine. Cu excepţia primei şi ultimei linii şi coloane, nu există pereţi |
| 2 | 7 | $N = 3$ |
| 3 | 12 | $S = 1$ |
| 4 | 23 | $S = 2$ |
| 5 | 41 | $1 ≤ N,M ≤ 250, 1 ≤ S ≤ 12$ |
| 6 | 14 | Nicio restricţie suplimentară |
 
 

* $... ≤ ... ≤ ...$

h2. Exemplu