Worst-Case Coin Collection

You are given a game played on an \(N \times M\) grid. Each cell in the grid is one of the following types:

• .: an empty cell.
• #: a wall cell.
• o: a coin cell.
• X: a bomb cell.
• S: a starting position.

The grid contains one or more starting positions (S). When the game begins, one of these starting positions is chosen arbitrarily. Because the map is dark, you can only see the \(3 \times 3\) square centered on your current position. In your vision, the cells with a bomb (X) and a starting position (S) are displayed as empty cells (.). Note that you cannot move into wall cells (#).

You can move one step at a time in the four cardinal directions (up, down, left, right). When you enter a cell with a coin (o), you collect one coin and that coin disappears from the grid. However, if you ever enter a cell with a bomb (X), you lose all the coins you have collected and the game immediately ends.

Your task is to determine, if you play optimally, what is the maximum number of coins you can guarantee in the worst-case scenario. In other words, among all possible starting positions, compute the maximum number of coins that can be collected without ever stepping into a bomb, assuming that an adversary chooses the starting position that minimizes your potential coin count.

Note: Although the description mentions limited vision, you are given the entire grid in the input. The bombs (X) are dangerous: if you step on one, you lose everything. Thus, an optimal strategy will avoid bombs by treating bomb cells as if they were walls. Similarly, walls (#) block movement. From any starting cell, the set of cells you may safely reach is determined by moving in the four directions while avoiding cells containing # or X. The coins collected in that accessible region form your final score if that region contains at least one starting position. Since the starting position is chosen arbitrarily among all S cells, the answer to the problem is the minimum coin count over all connected regions that contain at least one S cell.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns respectively).

Then follow \(N\) lines, each containing a string of length \(M\), representing the grid. The grid consists only of the characters ., #, o, X, and S.

outputFormat

Output a single integer: the maximum number of coins that can be guaranteed in the worst-case starting position (i.e. the minimum number of coins collectable among all connected regions that contain a starting position), assuming you avoid all bombs.

sample

3 3
S.o
...
..S

1