宿州市最近流行桌游。在一款桌游中，你进入了一个nxn大小的地牢。地牢中有一些格子：
空格，用"."表示；
小怪，用"#"表示。你的起点，用"S"表示（数据保证仅有一个起点）;
Boss，用"T"表示；
地牢祝福，用"!"表示。
探险的规则如下：
1．空格位置你可以走，且不会丢失血量；
2．小怪位置和 Boss 位置你可以走，但一旦走到有小怪或者 Boss的位置你必须与它们作战；
3．走到地牢祝福位置你会获得地牢祝福；
4．在击败 Boss之后会获得游戏胜利。
关于作战的规则如下：你先手，每回合你先对小怪或 Boss 造成与你攻击力相等的伤害，然后再由小怪或Boss对你造成与它攻击力相等的伤害，一直下去直到一方阵亡。
现在已知有 m+1个怪物，其中m个小怪1个Boss（在地牢地图中保证存在恰好 m个"#"和1个"T")；你的攻击力是A，到达地牢祝福位置会再给你加A点攻击力。给定上面这些信息，你活着的条件是任意时刻你的血量都大于0，求你能活着走出地牢的最少初始血量 B。
注意：你每经过一次有小怪的某个格子时，你都必须与该格子的小怪作战，即使你曾经击败过它。