Шифрування Муу#11166

Шифрування Муу

1 секунда

128 мегабайтів

Дуже легка

Мало хто знає, що корови дуже люблять головоломки, особливо словесні. Корови фермера Джона нещодавно вигадали кумедну головоломку "пошук слів". Приклад такої головоломки:

U O M P S O O Q O M O M P A M R E B X O N O O M

\begin{array}{llllll} U&S&O&P&E&N\\ O&O&M&A&B&O\\ M&O&O&M&X&O\\ P&Q&M&R&O&M \end{array}

Оскільки корови — всього лише корови, єдине слово, яке їх цікавить, — $M O O$ . Воно може зустрічатися в головоломці в найрізноманітніших місцях: горизонтально, вертикально або по діагоналі. У наведеному вище прикладі слово $M O O$ зустрічається $6$ разів.

Фермер Джон також любить головоломки зі словами. Оскільки корови не хочуть, щоб він розв'язав їхню головоломку раніше, ніж вони самі встигнуть спробувати, вони зашифрували її за допомогою «шифру підстановки», який замінює кожну літеру алфавіту на іншу літеру.

Наприклад, $A$ може бути замінена на $X$ , $B$ — на $A$ і так далі. Жодна літера не замінюється на саму себе, і жодні дві літери не замінюються на одну й ту саму літеру, оскільки в іншому випадку розшифрування було б неоднозначним.

На жаль, корови загубили інформацію про те, який саме шифр підстановки використовувався для шифрування їхньої головоломки. Допоможіть їм визначити максимально можливу кількість слів $M O O$ , яка могла міститися в головоломці при деякому допустимому варіанті шифру підстановки.

Вхідні дані

У першому рядку знаходяться два цілих числа $n$ і $m (1 \leq n, m \leq 50)$ m~(1 \le n, m \le 50), що позначають кількість рядків і стовпців головоломки.

Наступні $n$ рядків містять по $m$ символів, що описують відповідний рядок зашифрованої головоломки. Кожен символ є великою англійською літерою з діапазону $A \dots Z$ .

Вихідні дані

Виведіть максимально можливу кількість слів $M O O$ , яка може міститися в головоломці після її розшифрування за допомогою деякого відповідного шифру підстановки.

Приклади

Наведений приклад — це та сама головоломка, що і на початку умови, але до неї було застосовано шифр підстановки. У цьому прикладі літери $M$ і $O$ були замінені на $Q$ і $M$ відповідно.

Приклад 1