Description

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.

Input Format

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 Format

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

2 3 
..o 
o..

2

2 2 
oo 
oo

6

Hint

Explanation of Sample 1

..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 CONTEST 2 T2 MISA.

According to the original testdata configuration, the full score for this problem is $80$ points.

Translated by ChatGPT 5