Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Little Pigs and Wolves

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOnce upon a time there were several little pigs and several wolves on a two-dimensional grid of size *n* × *m*. Each cell in this grid was either empty, containing one little pig, or containing one wolf.

A little pig and a wolf are adjacent if the cells that they are located at share a side. The little pigs are afraid of wolves, so there will be at most one wolf adjacent to each little pig. But each wolf may be adjacent to any number of little pigs.

They have been living peacefully for several years. But today the wolves got hungry. One by one, each wolf will choose one of the little pigs adjacent to it (if any), and eats the poor little pig. This process is not repeated. That is, each wolf will get to eat at most one little pig. Once a little pig gets eaten, it disappears and cannot be eaten by any other wolf.

What is the maximum number of little pigs that may be eaten by the wolves?

Input

The first line contains integers *n* and *m* (1 ≤ *n*, *m* ≤ 10) which denotes the number of rows and columns in our two-dimensional grid, respectively. Then follow *n* lines containing *m* characters each — that is the grid description. "." means that this cell is empty. "P" means that this cell contains a little pig. "W" means that this cell contains a wolf.

It is guaranteed that there will be at most one wolf adjacent to any little pig.

Output

Print a single number — the maximal number of little pigs that may be eaten by the wolves.

Examples

Input

2 3

PPW

W.P

Output

2

Input

3 3

P.W

.P.

W.P

Output

0

Note

In the first example, one possible scenario in which two little pigs get eaten by the wolves is as follows.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2018 07:14:10 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|