题目背景

在 Minecraft Java 版中，空置域（Perimeter） 是指玩家为了刷怪效率而清理出的大片区域。

为了建造空置域，史蒂夫需要清除区域内的所有方块，包括空气方块和实体方块。现在，你需要帮助史蒂夫计算肝空置域所需的时间。

史蒂夫有一个耐久为 $-1$ 的盾牌，所以不会被 TNT 炸死。

（还有，史蒂夫作为肝帝当然是纯手挖啦）

题目描述

史蒂夫需要清理一个大小为 $n \times m$ 的区域。

区域中的每个方块可能是以下几种类型：

• 空气方块（Air）：用字符 . 表示，不需要清理。

• 实体方块（Block）：用字符 # 表示，需要清理。

• TNT 方块：用字符 T 表示，清理时会引爆，同时清除其周围 $8$ 个方向的方块（如果存在方块）。

清理规则：

• 清理一个实体方块需要 $1$ 单位时间。

• 清理一个 TNT 方块需要 $2$ 单位时间（包括举盾防御的时间），同时会引爆并清除其周围 $8$ 个方向的方块（如果存在方块）。

• 被 TNT 引爆的方块不需要额外时间清理。

请你计算清理整个 $n \times m$ 区域所需的最短时间。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示区域的大小。 接下来 $n$ 行，每行包含 $m$ 个字符，表示区域的布局。

输出格式

输出一个整数，表示清理整个区域所需的最短时间。

输入输出样例

3 3
.#.
T#.
.#.

2

4 4
.#.#
T#T#
.#.#
T#T#

8

说明 / 提示

样例 1 解释

清理 TNT 方块需要 $2$ 单位时间，同时引爆并清除其周围的实体方块（共 $3$ 个）。

剩余的空气方块不需要清理。

总时间为 $2$ 单位。

数据范围与约定

设方块对应字符为 $a_{i,j}$。

对于 $100\%$ 的数据，$1 \le n, m \le 1000, a_{i,j} \in \{\rm{.,T,\#}\}$。