The Painting Thief

A notorious thief has infiltrated a museum and must navigate a labyrinthine gallery represented as a grid. The grid is composed of various characters:

• #: Wall or obstacle (cannot be passed).
• E: Entry point (starting position).
• P: A painting that can be stolen (each counts as 1).
• .: Empty space (can be moved into).
• X: A trap (if stepped on, no further moves can be made from that cell).

Starting from the entry point, the thief can move in the four cardinal directions (up, down, left, right). The thief aims to steal as many paintings as possible along a single continuous path. However, once a cell is visited it is temporarily blocked for that path, and a trap ('X') halts further progress.

Your task is to determine the maximum number of paintings the thief can collect before either being caught by a trap or running out of moves.

The problem may involve backtracking and depth-first search where paths are explored recursively. Any mathematical notation needed (if any) must be written in LaTeX format.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
row_1
row_2
... 
row_n

where n and m are integers representing the number of rows and columns of the grid respectively. Each of the next n lines contains a string of length m representing a row of the grid.

outputFormat

Output a single integer to standard output (stdout) which represents the maximum number of paintings the thief can steal.

## sample

5 5
#####
#E.P#
#...#
#PX.#
#####

1