beecrowd | 2853

Bibika's Inventions

By Dâmi Henrique, Inatel BR Brazil

Timelimit: 1

Bibika, a nice mineira, was expelled from Brazil because she was bothering Brazilian politicians with her miraculous inventions. His last invention was the VDH (Honesty Virus) which, when in contact with a human, would make him an honest person forever (it would even work with politicians!).

After a few months wandering from country to country, she got a fixed home in China. One fine day, while taking photos at the Wall of China, she had an idea of how to spread the VDH in Brazil. Her idea was to spread some invisible robots (yes, she invented invisible robots) in the cities of Brazil and these robots would launch the VDH gradually (so it would not call so much attention) until all of Brazil was infected.

We will see Brazil as a NxM grid, where in some cells of this grid there will be a robot equipped with the VDH.

A robot is able to launch the virus to the four directions (North, South, East and West) and initially has a release power of 1. This means that on the first day it will infect 1 cell in each direction. With each new day its power increases by one unit, causing the robot on the third day, for example, to infect up to 12 cells, 3 in each direction.

Here is an example of the positions infected by a robot, represented by the character @, in a total of four days:

UOJ_383_G

Even after inventing the virus of honesty and invisible robots, Bibika does not know how many days it will take to infect the entire Brazilian territory, given a robot configuration. It is worth mentioning that cells that have robots are already automatically infected.

Your task is to help her in this mission or to say that it is not possible to infect all Brazil given the configuration of robots of Bibika.

Input

The first line contains two integers N and M (1 ≤ N, M ≤ 1000), representing the size of the map of Brazil.
Each of the next N lines will contain M characters '#' or '@', where '#' represents any area of Brazilian territory and '@' represents an area with an invisible robot from Bibika.

Output

Display a single integer, the number of days that will be needed to infect the entire Brazil. If this is impossible, print -1.

Sample Input Sample Output

5 6
#@##@#
#####@
##@###
###@##
@#####

4

2 2
@#
##

-1

2 2
@@
@@

0

3 3
@##

@##

#@#

2