27314번 - 러키☆한별

한별이는 운이 매우 좋다!

한별이는 벽, 다른 사람들, 그리고 여러 개의 출구가 있는 미로를 탈출하고자 한다.

미로 내에서 한별이와 다른 사람들은 매 순간 상하좌우 중 한 방향으로 한 칸 이동할 수 있다. 또, 한별이가 아닌 다른 사람들은 멈춰있을 수도 있다. 벽이 있는 칸으로 이동하거나 미로 격자 밖으로 나가는 것은 불가능하다. 여러 명이 같은 칸에 있는 것은 가능하다.

한별이를 제외한 사람들은 모두 한별이에게 줄 선물을 하나씩 가지고 있다. 만약 한별이와 선물을 가진 사람이 같은 칸에 있으면, 그 사람은 한별이에게 선물을 준다.

한별이는 한별이가 도달할 수 있는 미로의 출구 중 하나를 골라 이로 향하는 최단경로 중 하나를 고르고, 이를 따라 이동한다. 한별이를 제외한 다른 사람들은 한별이의 경로를 알고, 한별이에게 선물을 주기 위한 최적의 경로로 이동한다.

한별이가 어떤 칸에서 다른 칸으로 이동하면, 도착한 칸에 이미 있던 사람들과, 그 칸에 한별이와 동시에 도착한 사람들에게 선물을 받는다. 그 뒤 만약 도착한 칸이 한별이가 처음에 정한 출구면, 즉시 미로를 탈출한다. 다른 사람들은 어떤 출구에 도착해도 미로를 탈출하지 않는다.

한별이는 운이 매우 좋기 때문에, 항상 가능한 최대의 선물을 받는다. 한별이가 출구와 최단경로를 적절히 고르고, 사람들이 적절히 움직였을 때 한별이가 받을 수 있는 선물의 최대 개수를 구하시오.

첫 번째 줄에 미로의 높이 $N$과 너비 $M$이 공백으로 구분되어 주어진다. ($1 \leq N, M$, $N \times M \leq 100\, 000$)

다음 $N$개의 줄에 미로의 정보가 길이 $M$인 문자열로 주어진다.

문자열에서 H는 한별이를 뜻하고, 미로 안에 정확히 한 번 나타난다.

문자열에서 P는 한별이가 아닌 다른 사람을 뜻하고, 미로 안에 최소 $1$번, 최대 $100$번 나타난다.

문자열에서 #은 출구를 뜻하고, 미로 안에 최대 $100$번 나타난다.

문자열에서 .는 빈 공간을 뜻한다.

문자열에서 X는 벽을 뜻한다.

한별이가 도달할 수 있는 출구가 하나 이상 존재함이 보장된다.

한별이가 받을 수 있는 선물의 최대 개수를 출력한다.