Roman Catholic Mass

Interview

Time limit1sMemory limit128 MB

Summary

The program seats the latecomer in the empty spot with the most occupied neighbors and counts every adjacent occupied pair once.

Level: Easy2 of 10
Topics: Brute force, Matrix, Simulation
Solved: No attempts yet

Problem

The best moment of a Roman Catholic mass is the sign of peace, when people shake hands with each other and say "peace be with you".

The church has $R$ benches, one per row, and $S$ people fit on one bench. The seating of the church is therefore an $R \times S$ matrix, and each cell of the matrix says whether someone is sitting in that seat. Every person shakes hands with each of their neighbors. The neighbors of a seat are the people in the eight cells next to it. Along the edge some of those eight cells do not exist.

Sanggeun overslept again and came late to the mass, so he ran all the way to the church entrance to take part in the sign of peace, his favorite moment. Sanggeun takes the seat where he can shake the most hands. If no seat is left, he does not sit down and comes back for the evening mass instead. Nobody arrives later than Sanggeun.

You are given the seating of the church right before Sanggeun walks in. Write a program that computes how many handshakes happen in total during the sign of peace.

Input

The first line contains $R$ and $S$ . ( $1 \le R, S \le 50$ )

Each of the next $R$ lines contains $S$ characters. These $R \times S$ characters describe the seating of the church. A . is an empty seat and an o is a seat with a person in it.

Output

Print how many handshakes happen in total during the sign of peace.

Examples2

Example 1
Input
```
2 3
..o
o..
```
Expected output
```
2
```
Example 2
Input
```
2 2
oo
oo
```
Expected output
```
6
```