Коровы увлекаются словесными пазлами. Например, таким
USOPEN
OOMABO
MOOMXO
PQMROM
Как коровам, им интересно только единственное слово "MOO", которое может появиться во многих местах горизонтально, вертикально или по диагонали. Пример сверху содержит 6 таких слов.
Фермер Джон тоже любитель таких пазлов. Поскольку коровы не хотят, чтобы он разгадывал пазлы раньше коров, они зашифровали пазл, используя заменяющий шифр, который заменяет каждую букву алфавита некоторой другой, отличающейся буквой. Например, A может заменяться буквой X, B - буквой A и т.д. Никакая буква не заменяется собой и никакие две буквы не заменяются одной и той же буквой (иначе расшифровка может стать неоднозначной).
К несчастью, коровы потеряли свою таблицу шифрования и теперь не могут расшифровать свой пазл. Пожалуйста, помогите им определить максимально возможное количество слов MOO, которое может существовать для их пазла, при выборе соответствующей таблицы шифрования
ФОРМАТ ВВОДА :
Первая строка ввода содержит N и M, описывающие количество строк и столбцов в пазле (оба не более 50). Каждая из следующих N строк содержит по M символов, описывающих одну строку зашифрованного пазла. Каждый символ - большая латинская буква в диапазоне A..Z.
ФОРМАТ ВЫВОДА :
Выведите максимально возможное количество слов MOO, содержащееся в пазле, если его расшифровывать с соответствующей таблицей шифрования.
| Ввод |
Вывод |
|
4 6
TAMHGI
MMQVWM
QMMQSM
HBQUMQ
|
6 |
Пояснение
Это пазл, приведенный в начале задачи, где "M" и "O" были заменены на "Q" и "M" соответственно.