You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

本题为$\texttt{COCI 2009-2010}\ 2^\texttt{nd}\ \texttt{round}\ \text{T4 VUK}$。

分值按原题设置，满分 $100$。

题目描述

一匹狼 Vjekoslav 正在逃离一批残暴的猎人的追捕。

这些猎人非常凶残，经常躲在树后面，但 Vjekoslav 并不知道哪棵树后有猎人。为了保险，Vjekoslav 希望在逃回它舒适的窝的过程中离树越远越好。

森林可以抽象为 $N\times M$ 的矩阵。每个格子可能是空的（用.表示），也有可能有一棵树在中心位置（用+表示）。Vjekoslav在V标示的地方而它的窝在J标示的地方。定义 Vjekoslav 与某棵树的距离为它们所在格的曼哈顿距离（即这两个格子所在行、列之差的绝对值之和）。

Vjekoslav 每次可以往东南西北中的任一方向移动，即使它下一步移动到的格子有树（此题树并不会阻挡 Vjekoslav）。帮忙找出这样一条从V到J的路径，使得 Vjekoslav 在途中离它最近的树的距离的最小值最大。

注意 Vjekoslav 的窝并不占据整块格子，因此你的路径中必须包含J。

输入格式

第一行两个整数 $N,M$。

接下来 $N$ 行每行 $M$ 个字符，描述这片森林。

在这片森林的描述中，只会有一个V与一个J，且保证至少有一个+。

输出格式

一行一个整数，Vjekoslav 在逃回窝的途中最大可能的离它最近的树的距离的最小值。

4 4
+...
....
....
V..J

3

4 5
.....
.+++.
.+.+.
V+.J+

0

提示

$1\leq N,M\leq500$。