B. Ifrit Tile 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Does it hurt?

I BET IT DOES!

— a professional arsonist

Ifrit is an operator in Arknights who specializes in mapwide war crimes. You are tasked to increase the efficiency with which said war crimes are committed.

A map in Arknights can be represented as an $$$n$$$ by $$$m$$$ grid with three types of tiles:

  1. Placeable high-ground tiles (you can place Ifrit here). These tiles are denoted with a H.
  2. Low ground tiles (enemies walk here). These tiles are denoted with a L.
  3. Unplaceable high-ground tiles (you cannot place Ifrit here). These tiles are denoted with a #.

Let the upper-left tile be $$$(1, 1)$$$ and the bottom-right tile be $$$(n, m)$$$. We say a tile $$$(x, y)$$$ is an Ifrit Tile if the following conditions hold:

  • It is a placeable high-ground tile. We want to place down Ifrit.
  • We can pick a direction (up, left, down, right) such that out of the $$$5$$$ tiles immediately in that direction excluding the tile Ifrit is placed on, at least two of them are low-ground tiles. We want Ifrit to hit some enemies.

For a given map, count all Ifrit Tiles.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ denoting the length and width of the map $$$(1 \leq n, m \leq 1000)$$$.

The following $$$n$$$ lines each contain a string of length $$$m$$$, the $$$j$$$'th character on the $$$i$$$'th row being either an H, L, or #, denoting that tile $$$(i, j)$$$ is a tile of that type as defined in the statement.

—

Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10} = 10$$$ points.

Tests $$$1 - 3$$$ satisfy that $$$n, m \leq 10$$$.

The remaining tests do not satisfy any additional constraints.

Output

Output a single integer, denoting the number of Ifrit Tiles on the map.

Example
Input
5 7
##HLHH#
#HHLHH#
LLLLLLL
##HHLHH
##HHLH#
Output
4
Note

The Ifrit Tiles are $$$(1, 5)$$$, $$$(2, 5)$$$, $$$(4, 4)$$$, and $$$(5, 4)$$$. Ifrit should be placed facing down, down, up, and up respectively on these tiles to hit at least two low-ground tiles.

This map is also the stage $$$1-1$$$ in Arknights.

—

Problem Idea: willy108

Problem Preparation: willy108

Occurrences: Novice B