E - 更强的高桥

给定一个由$H$行$W$列组成的网格，网格中的第$i$行第$j$列的格子是可以通过的，当$S_{i,j}$等于.时，并且该格子是一个障碍物，当$S_{i,j}$等于#时。高桥要从他的家走到一个鱼市场，高桥的家在左上角的格子，鱼市场在右下角的格子。

高桥可以向上、下、左、右移动到一个可以通过的格子，但不能离开这个城镇，他也不能进入障碍物。然而，他的体力可以一拳将一个$2\times 2$格子区域内的所有障碍物摧毁，使这些格子变为可以通过的。

找出高桥到达鱼市场所需的最小拳击次数。

输入

从标准输入中读入数据，输入的格式如下：

$H$ $W$

$S_{1,1} \ldots S_{1,W}$

$\vdots$

$S_{H,1} \ldots S_{H,W}$

输出

输出答案。

样例解释

【样例 1】

高桥可以通过摧毁一个$2\times 2$格子区域内的障碍物到达鱼市场，例如，他可以摧毁下图所示的$2\times 2$格子区域内的障碍物：

..#..
#.**#
##**#
#.#.#
..#..

注意：并不要求待摧毁的区域中所有的$2\times 2$格子都是障碍物。

【样例 2】

高桥可以不摧毁任何障碍物就到达鱼市场，尽管他必须绕远路。

【样例 3】

高桥需要摧毁5个区域内的障碍物才能到达鱼市场。