Lucky☆Hanbyul

Hanbyul is very lucky!

Hanbyul wants to escape a maze that has walls, other people, and several exits.

Inside the maze, Hanbyul and the other people can each move one cell up, down, left, or right at every moment. People other than Hanbyul may also stay still. Moving into a wall cell or out of the grid is impossible. Several people can be in the same cell.

Every person except Hanbyul holds one gift for Hanbyul. If Hanbyul and a person holding a gift are in the same cell, that person gives the gift to Hanbyul.

Hanbyul picks one of the exits that Hanbyul can reach, picks one of the shortest paths to it, and follows that path. The other people know Hanbyul's path and move along the optimal routes to give Hanbyul their gifts.

When Hanbyul moves from one cell to another, Hanbyul receives gifts from the people already in the arrived cell and from the people who arrived in that cell at the same time as Hanbyul. If the arrived cell is the exit Hanbyul chose at the start, Hanbyul escapes the maze immediately. The other people do not escape the maze even if they reach an exit.

Hanbyul is very lucky, so Hanbyul always receives the maximum possible number of gifts. Find the maximum number of gifts Hanbyul can receive when Hanbyul chooses an exit and a shortest path appropriately and the other people move appropriately.

The first line contains the height $N$ and width $M$ of the maze, separated by a space. ($1 \leq N, M$, $N \times M \leq 100\,000$)

The next $N$ lines give the maze as strings of length $M$.

In the strings, H marks Hanbyul and appears exactly once in the maze.

In the strings, P marks a person other than Hanbyul and appears at least 1 time and at most 100 times in the maze.

In the strings, # marks an exit and appears at most 100 times in the maze.

In the strings, . marks an empty cell.

In the strings, X marks a wall.

At least one exit that Hanbyul can reach is guaranteed to exist.

Print the maximum number of gifts Hanbyul can receive.