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 x 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ă.

Cerința

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?

Date de intrare

Pe prima linie a intrării standard 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ţ.

Date de ieșire

La ecran se va afişa un singur număr natural, numărul maxim de monezi care se poate obţine garantat pe acel teren.

Restricții și precizări

• Fie S numărul de celule de start ce se află pe hartă. N ≤ 400, M ≤ 400, S ≤ 60.
• Pentru 3 puncte, S = 1, nu există mine și cu excepția primei și ultimei coloane și nu există pereți.
• Pentru 7 puncte, N = 3
• Pentru 12 puncte, S = 1
• Pentru 23 puncte, S = 2
• Pentru 41 puncte, 1 ≤ N, M ≤ 250, 1 ≤ S ≤ 12
• Pentru 14 puncte, nicio restricție suplimentară

Exemplul 1:

Intrare

3 7
#######
#Soooo#
#######

Ieșire

4

Explicație

Există o singură poziție de start, deci știm exact de unde va porni jucătorul. În acest caz, jucătorul poate colecta toate monezile.

Exemplul 2:

Intrare

3 8
########
#SoXooS#
########

Ieșire

1

Explicație

Sunt două poziții de start, iar jucătorul poate deduce unde este poziționat pe baza zonei de vizibilitate (P este poziția jucătorului):

### ###
#Po oP#
### ###

Numărul maxim de monezi pe care le poate colecta jucătorul dacă pornește din partea stângă este 1, respectiv 2 dacă pornește din partea dreaptă. Deci, pe cel mai rău caz, putem colecta o monedă.

Exemplul 3:

Intrare

7 18
##################
#................#
#.o...SX.......o.#
#.o...X..X.....o.#
#.o.....XS.....o.#
#................#
##################

Ieșire

0

Explicație

În orice direcţie s-ar mişca iniţial jucătorul, pe caz nefavorabil se va afla o mină în direcţia respectivă.
Zona de vizibilitate iniţială este (P este poziția jucătorului):

...
.P.
...

Exemplul4:

Intrare

7 18
##################
#....#...........#
#.o...SX.......o.#
#.o...X..X.....o.#
#.o.....XS.....o.#
#.........#......#
##################

Ieșire

6

Explicație

Jucătorul îşi poate da seama în care celulă a fost plasat iniţial, analizând zona de vizibilitate. Mai exact, acesta se uită dacă iniţial vede un perete în stânga-sus sau dreapta-jos; astfel, ştie exact cum să se poziţioneze pentru a evita minele. Zonele de vizibilitate iniţiale aferente celor două poziţii sunt (P este poziția jucătorului):

#.. ...
.P. .P.
... ..#

Exemplul 5:

Intrare

7 18
##################
#......X..S....oo#
##################
#..o..S.X......o.#
##########X#######
#o.....S...X.....#
##################

Ieșire

1

Explicație

Jucătorul se mută 2 paşi la stânga. Dacă vede o monedă la stânga, deduce că este în zona din mijloc, o culege şi termină jocul. Dacă nu, ştie că nu este în zona din mijloc, aşa că se mută la dreapta 4 pași. Observând mai apoi dacă există spaţiu liber în dreapta-sus (minele sunt văzute drept spaţii libere), poate deduce dacă se află în zona de sus sau zona de jos. În ambele cazuri, este liber să colecteze moneda/monezile corespunzătoare. În cel mai nefavorabil caz, însă, va putea colecta o singură monedă. Se poate observa că jucătorul nu se putea muta iniţial spre dreapta, deoarece ar fi riscat să atingă mina din centru pe caz nefavorabil.