暂无测试数据。

题目描述

Alice 住在森林里，
森林可以看作是 \(N*M\) 的网格，
森林里有怪兽，

• '.' 表示空地
• '+' 表示怪兽
• 'V' 表示Alice现在的位置
• 'J' 表示Alice的家。

Alice 可以从当前单元格向上下左右相邻单元格移动，
有怪兽的地方也可以走，
只不过比较危险，
有怪兽的单元格对其他单元格会产生一定的危险系数，
假设怪兽位置为 \((A,B)\)，
它对某单元格 \((R,C)\) 的危险系数为：\(|R-A|+|C-B|\)，
危险系数越小越危险，
每个单元格的危险系数是所有怪兽对它产生的系数的最小值。
Alice 请你帮她找一条最佳路径回家，
即使得路径上经过单元格的最小的危险系数最大。

输入

第一行，包含两个整数 \(N\) 和 \(M\)，表示森林的大小。
接下来 \(N\) 行每行包含 \(M\) 个字符：'.'，'+'，'V'，'J'。
输入只包含一个 'V' 和 'J'，而且至少有一个'+'。

输出

输出最佳路径中最小的危险系数。

样例 1

输入

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

输出

3

样例 2

输入

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

输出

0

数据范围限制

\(1 \leq N,M \leq 500\)

来源

基础篇补充7.13