Wyprzedaż

Pod Warszawą otworzyli nowy sklep z akcesoriami elektronicznymi. Postanowiłeś się wybrać na otwarcie, jednak okazało się, że nie tylko Ty wpadłeś na tak genialny pomysł. Ludzi jest pełno, a Ty chcesz się dostać do stoiska z CD-ROMami na wagę. Patrząc na sklep przez szybę narysowałeś plan sklepu, teraz tylko pozostało wyciągnąć z plecaka laptopa i napisać program, który Ci znajdzie najszybszą drogę dostania się do stoiska z CD-ROMami na wagę...

Wejście, wyjście

Sklep ma kształt prostokąta x na y, 1 <= x,y <= 25. W pierwszej linii wejścia są liczby x i y, oddzielone pojedynczą spacją. Kolejne y linii zawiera po x znaków każda, każdy znak opisuje pojedyncze pole w sklepie:

Przechodzić możesz tylko między polami sąsiadującymi bokiem. Przejście przez pole S i D zajmuje zaniedbywalnie mało czasu.

W jednej jedynej linijce wyjścia powinieneś wypisać jedną liczbę całkowitą - minimalny czas potrzebny do dostania się do stoiska z CD-ROMami na wagę. Załóż, że zawsze jakoś się da tam przepchać.

Przykład

Dane:

5 5
S5213
2X2X5
51248
4X4X2
1445D

dają odpowiedź:

23