Parking#2903

Parking

1 second
128 megabytes
Very easy

In a parking lot, there are several cars and parking spots. Every car needs to find a parking spot. Due to traffic regulations, each car may move only parallel to the boundaries of the parking lot and only at the speed of one square per unit of time.

Usually, cars go to the nearest available parking spot, but this may not always be optimal for every car. Consider the following parking lot (where 'C' is a car, 'P' is a parking spot, 'X' is a wall, and '.' is an empty space):

.C.....P.X...

XX.......X..P

XX.....C.....

If the car on the bottom moves to the nearest parking spot, the car on the upper left has to travel all the way to the right, taking units of time. However, if the car on the bottom goes to the right parking spot, both cars can reach parking spots in units of time.

Find the minimal time required for all cars to park (assuming the cars act as described above). All cars start from an empty space. Cars are small enough that any number of them can be on the same square simultaneously. They can move over empty spaces and parking spots, but not through walls. Each parking spot must be occupied by at most one car at the end.

Input

The input consists of multiple test cases. Each test case starts with a line containing two integers and (1 \leq row, column \leq 50) — the dimensions of the parking lot. The next lines describe the parking lot as mentioned above. The number of cars and parking spots in each test case does not exceed .

Output

For each test case, print in a separate line the minimal amount of time required for all cars to get to parking spots. If it is impossible for every car to reach a parking spot, print -1. If there are no cars in the parking lot, print 0.

Examples

Example 1

Loading
Loading