Icpca 的女王在城堡中过着平静的生活。有一天，她听说许多特工在其他国家活动，便开始担心城堡的安全。

这座城堡有一个矩形地牢，由 $h$ 行 $w$ 列的正方形房间组成。相邻的房间之间由墙壁隔开。有些墙壁上有门，使得相邻的房间可以互通。地牢的入口和出口位于两个对角线极端的房间。地牢的房间构成了一棵树，也就是说，从地牢中的每个房间出发，都有且仅有一条路径可以到达出口，且该路径经过路径上的所有房间且仅经过一次。

为了加强城堡的安全性，女王想要改造地牢，使得从入口房间到出口房间的路径上的房间数量最大化。她喜欢当前地牢的树状结构，因此必须保留这一特性。由于成本限制，改造过程中只能封堵一个现有的门使其无法通行，并在墙上新建一个门（可能是在同一面墙上）。

你的任务是找到一种符合女王要求的地牢改造方法。

输入格式

输入包含单个测试用例，格式如下：

$h$ $w$ $c_{1,1}c_{1,2} \dots c_{1,2w+1}$ $c_{2,1}c_{2,2} \dots c_{2,2w+1}$ $\vdots$ $c_{2h+1,1}c_{2h+1,2} \dots c_{2h+1,2w+1}$

$h$ 和 $w$ 表示地牢的大小，均为 $2$ 到 $500$ 之间的整数。字符 $c_{i,j}$ ($1 \le i \le 2h + 1, 1 \le j \le 2w + 1$) 表示地牢的结构，具体如下：

• $c_{2i,2j} = \text{‘.’}$，其中 $1 \le i \le h$ 且 $1 \le j \le w$，对应于从北端起第 $i$ 行、从西端起第 $j$ 列的房间；这样的房间称为房间 $(i, j)$。
• $c_{2i+1,2j} = \text{‘.’}$ 或 $\text{‘-’}$，其中 $1 \le i \le h - 1$ 且 $1 \le j \le w$，表示房间 $(i, j)$ 和 $(i + 1, j)$ 之间的墙壁；字符 $\text{‘.’}$ 表示墙上有门，$\text{‘-’}$ 表示没有门。
• $c_{2i,2j+1} = \text{‘.’}$ 或 $\text{‘|’}$，其中 $1 \le i \le h$ 且 $1 \le j \le w - 1$，表示房间 $(i, j)$ 和 $(i, j + 1)$ 之间的墙壁；字符 $\text{‘.’}$ 表示墙上有门，$\text{‘|’}$ 表示没有门。
• $c_{1,2j} = c_{2h+1,2j} = \text{‘-’}$ ($1 \le j \le w$) 以及 $c_{2i,1} = c_{2i,2w+1} = \text{‘|’}$ ($1 \le i \le h$)，对应于地牢的外墙。
• $c_{2i+1,2j+1} = \text{‘+’}$，其中 $0 \le i \le h$ 且 $0 \le j \le w$，对应于墙壁或外墙的交点。

入口和出口分别位于房间 $(1, 1)$ 和 $(h, w)$。该结构满足上述树状特性。

输出格式

输出改造后从入口房间到出口房间可达到的最大路径长度，其中路径长度是指经过的房间数量（包含入口和出口房间）。

样例

样例输入 1

2 3
+-+-+-+
|.....|
+.+.+.+
|.|.|.|
+-+-+-+

样例输出 1

6

样例输入 2

2 3
+-+-+-+
|...|.|
+.+.+.+
|.|...|
+-+-+-+

样例输出 2

4

样例输入 3

5 5
+-+-+-+-+-+
|...|...|.|
+-+.+.+.+.+
|...|.|.|.|
+.+.+.+-+.+
|.|...|.|.|
+.+.+-+.+.+
|.|.....|.|
+-+.+.+-+.+
|...|.....|
+-+-+-+-+-+

样例输出 3

15

说明

在第一个样例中，如果封堵房间 $(1, 1)$ 和 $(1, 2)$ 之间的门，并在房间 $(2, 1)$ 和 $(2, 2)$ 之间新建一个门，那么从 $(1, 1)$ 到 $(2, 3)$ 的唯一路径将经过全部 6 个房间，这显然是最大值。

在第二个样例中，任何改造方案都使得从 $(1, 1)$ 到 $(2, 3)$ 的唯一路径长度保持为 4。

在第三个样例中，最优方案之一是封堵房间 $(4, 2)$ 和 $(4, 3)$ 之间的门，并在房间 $(2, 4)$ 和 $(3, 4)$ 之间新建一个门。