小杜捕鱼

题号：NC247478
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小杜闲着无聊，决定冲刺“捕鱼达人”中的隐藏成就“一网捕尽”！
已知一个 $n \times m$ 的矩形鱼塘和其中所有鱼的位置，小杜需要一网捕捞所有的鱼。已知 $k$ 级网可以捕捉距撒网中心曼哈顿距离不超过 $k$ 的所有鱼。
曼哈顿距离：我们定义两个点 $(x0,y0)$ 与 $(x1,y1)$ 的曼哈顿距离为 $|x0-x1|+|y0-y1|$ 。

如下图为3级渔网有效范围：

然而小杜游戏水平并不那么高超，他的撒网中心位置可能落在矩形鱼塘中的任意位置。

求小杜需要准备的渔网的最低等级，即求k的最小值，以确保不论小杜将网撒在哪里，都一定能一网捕捞所有的鱼。

（假设游戏过程中，所有鱼以及撒网中心的坐标均为整数坐标，且都位于 $n\times m$ 的矩形鱼塘中）

输入描述:

第一行包括两个正整数；
接下来行，每行一个长为的仅包含字符’.’和’#’的字符串，’.’表示该单元格内没有鱼，’#’表示该单元格内有鱼。

输出描述:

输出一个非负整数，代表小杜需要准备的渔网的最低等级 $k$ 。

示例1

输入

复制

3 3
...
.#.
...

输出

复制

示例2

输入

复制

3 3
#..
...
...

输出

复制

示例3

输入

复制

1 1
#

输出

复制