AlgoLiga 2018

Ulubioną grą Stasia i Grzesia jest ich własna wersja gry Scrabble. W grze obowiązują następujące zasady:

1. Chłopcy przed rozpoczęciem każdej partii ustalają ile łącznie wyrazów ułożą na planszy. Liczba wyrazów zawsze jest z przedziału od 2 do 10 włącznie.
2. Grę rozpoczyna dowolny z chłopców.
3. Chłopcy układają wyrazy na zmianę.
4. Każdy kolejny wyraz musi być połączony z już istniejącym(i) i ułożony do niego/nich prostopadle. Gwarantuje to, że w każdym ruchu powstanie dokładnie jeden nowy wyraz. Oczywiście reguła ta nie dotyczy pierwszego układanego wyrazu.
5. Punkty przyznawane są za każdy wyraz ułożony poziomo albo pionowo.
6. Podstawowa wartość wyrazu to suma punktów przyznanych za każdą literę. Za samogłoskę (A,E,Y,U,I,O) dodajemy 1 punkt, zaś za spółgłoskę 3 punkty.
7. Do podstawowej wartości wyrazu doliczane są premie literowe, a następnie słowne.
8. Na planszy występują dwa rodzaje premii literowych:
   1. podwójna - oznaczona znakiem 2 - wartość litery wzrasta dwukrotnie
   2. potrójna - oznaczona znakiem 3 - wartość litery wzrasta trzykrotnie
9. Oraz dwa rodzaje premii słownych:
   1. podwójna - oznaczona znakiem D - wartość wyrazu wraz z uwzględnieniem premii literowych i innych premii słownych wzrasta dwukrotnie
   2. potrójna - oznaczona znakiem T - wartość wyrazu wraz z uwzględnieniem premii literowych i innych premii słownych wzrasta trzykrotnie
10. Na planszy może wystąpić dowolna liczba pól premii literowych oraz słownych.
11. Wynik gracza to suma wartości wszystkich ułożonych przez niego wyrazów z uwzględnieniem premii literowych oraz słownych.

Chłopcy właśnie zakończyli kolejną emocjonującą partię i mieli wziąć się za zliczanie punktów, kiedy uświadomili sobie, że żaden z nich nie zapisywał układanych przez siebie wyrazów ani cząstkowych wyników, nie pamiętają nawet kto rozpoczął grę. Na całe szczęście zasady ich wersji gry zdecydowanie ułatwiają odtworzenie przebiegu rozgrywki i nasi bohaterowie zamierzają z tego skorzystać. Grześ zamierza z tego skorzystać zdecydowanie bardziej niż Staś i poprosił Cię o napisanie programu, który obliczy ile maksymalnie punktów można było zdobyć układając co drugi wyraz. Oczywiście nie zamierza on odtwarzać rzeczywistego przebiegu rozgrywki, lecz takiego, w którym zdobywa on maksymalną możliwą liczbę punktów, a rozgrywka przebiega zgodnie z wymyślonymi przez chłopców zasadami.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite a i b (2 ≤ a, b ≤ 30) określające rozmiar planszy do gry. W kolejnych a liniach znajduje się po b znaków opisujących premie występujące na planszy:

• 0 - brak premii
• 2 - podwójna premia literowa
• 3 - potrójna premia literowa
• D - podwójna premia słowna
• T - potrójna premia słowna

W następnych a liniach znajduje się po b znaków opisujących wyrazy ułożone na planszy. Każdy znak to . oznaczająca puste pole albo wielka litera alfabetu angielskiego.

Wyjście

Na wyjściu należy wypisać maksymalną możliwą liczbę punktów jaką mógł zdobyć Grześ.

Przykład

Wejście

4 5
002TD
T0030
0230D
30D20
.ALGO
..I..
..G..
START

Wyjście

110