Moocryption

Interview

Time limit1sMemory limit256 MB

Summary

Find the substitution cipher with no fixed letters that yields the most MOO strings in all eight grid directions.

Level: Medium5 of 10
Topics: Brute force, Matrix, String matching
Solved: No attempts yet

Problem

Cows like puzzles, and word search puzzles most of all. Here is an example of the word finder that Farmer John's cows built.

USOPEN
OOMABO
MOOMXO
PQMROM

The only word the cows care about is "MOO". It can appear anywhere in the grid, and all eight readings count: horizontal, vertical and the two diagonals, each in both directions. The puzzle above contains 6 MOOs.

Farmer John likes word puzzles too. The cows do not want him to solve theirs first, so they encrypted the contents with a substitution cipher that replaces every letter of the alphabet with a different letter. For example, A might become X and B might become A. No letter maps to itself, and no two letters map to the same letter, because decryption would otherwise not be unique.

The cows have since lost the substitution cipher needed to decrypt the puzzle. Given the encrypted puzzle, find the largest number of MOOs it can contain for a suitable choice of substitution cipher.

Input

The first line contains $N$ and $M$ , the number of rows and columns of the puzzle. Both are between 1 and 50.

Each of the next $N$ lines contains $M$ characters, one row of the encrypted puzzle. Every character is an uppercase letter from A to Z.

Output

Print, on one line, the maximum number of MOOs the puzzle can contain for a suitable choice of substitution cipher.

Hint

The first sample input is the puzzle from the statement after a cipher was applied. Here M was replaced with Q and O was replaced with M.

Examples2

Example 1
Input
```
4 6
TAMHGI
MMQVWM
QMMQSM
HBQUMQ
```
Expected output
```
6
```
Example 2
Input
```
1 3
MOO
```
Expected output
```
0
```