Ir izcēlies ugunsgrēks! Tas izplatās un apdraudēto māju iemītniekiem ir jābēg izglābties. Jums ir iedota karte, kas dota kā rūtiņu laukums, kur katra rūtiņa ir 100 × 100 metrus liela. Katrā rūtiņa atzīmēta sekojoši:

1. '*' laukums nedeg, bet var aizdegties;
2. 'F' laukums jau deg;
3. 'X' uz laukuma ir klintis, tās aizdegties nevar, taču arī cilvēki nevar tās šķērsot vai tur patverties;
4. 'H' laukums ir nedegošs un uz tā var paglābties cilvēki;
5. '+' laukums nedeg bet var aizdegties, un uz tā atrodas viens cilvēks.

Ārpus kartes arī atrodas klintis, līdz ar to ne cilvēki, ne uguns to šķērsot nevar.

Minūtes laikā cilvēks var aizskriet uz vienu no 4 blakus esošajām rūtiņām (rūtiņām ar kopīgu malu), ja uz tās nav klintis. Kā arī katru minūti uguns izplatās uz tā 8 blakus esošajām rūtiņām (rūtīņām ar kopīgu malu vai stūri), ja šīs rūtiņas nav klintis vai patvērums. Līdz ar to situācija notiek sekojoši: cilvēki bēg, uguns izplatās, cilvēki bēg, uguns izplatās, cilvēki bēg un tā tālāk. 

Pieņemot, ka katrs cilvēks izvēlās optimālu bēgšanas taktiku, nosakiet, kāds ir lielākais cilvēku skaits, kas var izdzīvot.

Pirmajā rindā dots kartes izmēri veseli skaitļi n (rindu skaits) un m (kolonnu skaits) (1 ≤ n, m ≤ 500).

Tālāk seko n rindas ar m simboliem, kas apraksta karti atbilstoši dotajiem apzīmējumiem.

Izvadiet vienu veselu skaitli, lielāko cilvēku skaitu, kas var palikt dzīvi.

Uzdevumā var iegūt daļējus punktus:

• 30% testu n, m ≤ 32.

• 100% testu ar ievaddatos dotajiem limitiem.