Problem description

Wizyta na kontynentach oddalonych od Europy o Ocean Atlantycki dłużyła się Karolowi; postanowił więc, że już czas wracać do domu. Kupił możliwie najszybszy bilet lotniczy do Warszawy i tak się akurat złożyło, że był z kilkugodzinną przesiadką w Paryżu; nasz podróżnik nie mógł oczywiście zmarnować okazji do krótkiego zwiedzania stolicy Francji.

Karol postanowił wybrać się na Pola Elizejskie, na których właśnie odbywał się festiwal Bomb Francuskich – słynny na cały świat pokaz fajerwerków.

Pola Elizejskie mają kształt prostokątnego placu o wymiarach N × M metrów i mogą zostać w oczywisty sposób podzielone na N ⋅ M kawałków jednostkowych. Kawałek jednostkowy może być jednoznacznie wyznaczony poprzez podanie jego współrzędnych X i Y. Władze umieściły już na niektórych kawałkach jednostkowych placu fajerwerki dwóch różnych typów: HS – Hałaśliwych Serpentyn i AL – Ambrozji Leistej.

Fajerwerki typu HS mają moc R_HS i gdy wybuchają, to pokrywają niebo nad wszystkimi kawałkami jednostkowymi placu, które odległe są w metryce Manhattan o nie więcej niż R_HS – jeśli wystrzelony zostaje fajerwerk typu HS z kawałka jednostkowego o współrzędnych X_F i Y_F, to pokrywa wszystkie kawałki jednostkowe Pola Elizejskiego, których współrzędne X_P i Y_P spełniają zależność |X_F−X_P| + |Y_F−Y_P| ≤ R_HS.

Fajerwerki typu AL mają moc R_AL i gdy wybuchają, to pokrywają niebo nad wszystkimi kawałkami jednostkowymi placu, które odległe są w metryce Maksimum o nie więcej niż R_AL – jeśli wystrzelony zostaje fajerwerk typu AL z kawałka jednostkowego o współrzędnych X_F i Y_F, to pokrywa wszystkie kawałki jednostkowe Pola Elizejskiego, których współrzędne X_P i Y_P spełniają zależność max(|X_F−X_P|,|Y_F−Y_P|) ≤ R_AL.

Niestety ze względu na konieczność powrotu na lotnisko, jak i faktu opóźnienia się pokazu przez warunki atmosferyczne, Karol nie doczekał się wystrzału fajerwerków. Teraz zastanawia się nad tym, jak duże były ich moce. Podróżnik jest pewien, że po pierwsze fajerwerki pokryły niebo nad każdym kawałkiem jednostkowym Pola Elizejskiego; a po drugie, że ze względu na ograniczony budżet suma mocy fajerwerków R_HS i R_AL była najmniejsza możliwa.

Twoim zadaniem będzie napisanie programu, który wczyta rozłożenie fajerwerków na Polu Elizejskim i wyznaczy minimalną sumę mocy fajerwerków R_HS i R_AL, dla której możliwe jest pokrycie nieba nad każdym kawałkiem jednostkowym Pola Elizejskiego.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i oznaczające odpowiednio wysokość i szerokość Pola Elizejskiego. W każdym z kolejnych N wierszy znajduje się ciąg M znaków określających zawartość poszczególnych kawałków jednostkowych Pola Elizejskiego:

• . – oznacza kawałek jednostkowy, na którym nie został umieszczony żaden fajerwerk,
• A – oznacza kawałek jednostkowy, na którym umieszczony został fajerwerk typu AL,
• H – oznacza kawałek jednostkowy, na którym umieszczony został fajerwerk typu HS.

Zagwarantowane jest, że na Polu Elizejskim znajduje się przynajmniej jeden fajerwerk.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna suma mocy fajerwerków R_HS i R_AL, dla której możliwe jest pokrycie nieba nad każdym kawałkiem jednostkowym Pola Elizejskiego.

Ograniczenia

1 ≤ N, M ≤ 1 000.

Przykład

5 13
.............
.H...........
........A....
.H...........
.............

7