P7749 [COCI 2013/2014 #2] MISA

There is an $R \times S$ grid. Each person sits in one cell, and some cells may be empty. Each person will shake hands with the people in the **eight surrounding cells** (possibly fewer than $8$ people). Mirko arrives last, and he sits down as follows: - If there is an empty seat, he will choose an empty cell that lets him shake hands with the largest number of people. - If there is no empty seat, he will leave. Find the total number of handshakes after Mirko sits down.

The first line contains two integers $R, S$. Next is a character matrix with $R$ rows and $S$ columns describing the seating: - `.` means an empty seat. - `o` means the seat is occupied.

Output one integer in a single line: the total number of handshakes after Mirko sits down.

#### Explanation of Sample 1 ```plain ..o oo. ``` is one possible final seating arrangement that satisfies the requirement. #### Constraints - For $20\%$ of the data, $R = 1$. - For another $20\%$ of the data, $R = 2$. - For another $20\%$ of the data, all seats are occupied. - For $100\%$ of the data, $1 \le R, S \le 50$. #### Source **This problem is translated from [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T2 MISA_.** According to the original testdata configuration, the full score for this problem is $80$ points. Translated by ChatGPT 5