最近哪吒之魔童闹海电影十分火爆，小劉打算看看它的票房最终能够达到多少?

题目描述

该题目为Watching ( Easy ) 的困难版本，其中只有部分不同，未避免出现歧义，建议重新阅读题面。

我们现在拥有一个棋盘，对于给定的n行m列的范围，一共有 n * m 个位置可以放置物品。我们使用 ( i , j ) 表示范围中从商往下数第 i 行和从左往右数第 j 列的单元格，使用 s ( i , j ) 表示这个单元格的状态，状态有且仅有三种：

~若s ( i , j ) = ‘ P ’ ，表示第 i 行第 j 列中有一名观众。

~若s ( i , j ) = ‘ T ’ ，表示第 i 行第 j 列中有1个亿的票房。

~若s ( i , j ) = ‘ B ’ ，表示第 i 行第 j 列当前为空的单元格。

每一个单元格只能放置一名观众或1个亿的票房。若观众将票房连接起来的一个亿或多个亿票房组成的整体^注解包围，则这些票房将算作哪吒之魔童闹海的票房。初始状态可能会出现被包围的情况，你需要将其计算为已经获得的票房。

现在你可以选择任意一个为空的单元格放置一名观众，求解在最优策略下，你可以帮助哪吒之魔童闹海获得多少的票房。

注解：相邻的票房会被连接成为一个整体，当| x – x’ | + | y – y’ | = 1时，这两个相邻单元格中的票房被视为相邻被连接在一起，最终某个票房的整体相邻的没有空白单元格时，视为被观众包围。

输入描述

每组测试数据描述如下：

第一行两个正整数n，m（3 <= n , m <= 10³）代表棋盘的边长

后边的n行，每行m个字符，仅有字符 ‘ P ’ , ’ T ’ , ’ B ’构成的字符串,代表棋盘中每个单元格的初始状态。

输出描述

求解在最优策略下，你可以帮助哪吒之魔童闹海获得多少的票房。

样例

3 3
PPP
TTP
BTP

3

解释

在样例所给的棋盘中，' T ' 没有 ' P ' 被包围，然后你可以在(3,1)下一步' P '，最终答案即为最优解。

限制范围

每个测试样例限制为1s, 248Mb。