Parking Lot

The parking lot is a rectangular grid with R rows and C columns. It contains N cars and M parking regions. Every car must be assigned to a parking region. Because of traffic restrictions, cars can move only in the four directions parallel to the grid edges, and each car moves one cell per second.

Sending each car to the closest parking region is not always optimal. Consider this parking lot:

.C.....P.X...XX.......X..PXX.....C.....

C is a car, P is a parking region, X is a wall, and . is an empty cell.

If the lower car parks in the closest parking region, the upper-left car must use the far-right parking region, so that car needs 14 seconds. If the lower car instead uses the right parking region, both cars can finish parking within 6 seconds.

Given the shape of the parking lot, the car positions, and the parking-region positions, find the minimum possible time until every car is parked in a distinct parking region. Cars are very small, so several cars may occupy the same cell at the same time while moving. Cars may pass through empty cells and parking regions, but not through walls.

If it is impossible to park every car, output -1.

The first line contains the parking lot size R and C. Both R and C are at most 50.

Each of the next R lines describes one row of the parking lot using the characters explained above. The number of cars and the number of parking regions are each at least 0 and at most 100.

Print the minimum time needed until every car is parked. If there are no cars, print 0. If parking every car is impossible, print -1.