1712: 地牢探险
金币值：2
定数：1
时间限制：1.000 s
内存限制：128 M
正确：0
提交：0
正确率：0.00% 命题人：
题目描述
宿州市最近流行桌游。在一款桌游中，你进入了一个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。
注意：你每经过一次有小怪的某个格子时，你都必须与该格子的小怪作战，即使你曾经击败过它。
输入格式
第一行输入一个正整数T，表示数据组数。对每组数据，第一行输入三个整数 n,m,A,含义如题。
接下来输入一个nxn的字符矩阵，可能包含"'.","#","S"',"T","!"五种字符，表示地牢地图。并保证图中存在：一个"S"、一个"T"、一个"!"若干个"."和"#"，后两种字符可能不存在，其中"#"的个数一定是m个。
接下来输入m+1行，每行两个整数ai,bi，按照从上到下、从左到右的顺序依次给小怪编号，第i个小怪的攻击是ai，血量是bi。我们约定Boss的攻击是am+1, 血量是bm+1
接下来输入一个nxn的字符矩阵，可能包含"'.","#","S"',"T","!"五种字符，表示地牢地图。并保证图中存在：一个"S"、一个"T"、一个"!"若干个"."和"#"，后两种字符可能不存在，其中"#"的个数一定是m个。
接下来输入m+1行，每行两个整数ai,bi，按照从上到下、从左到右的顺序依次给小怪编号，第i个小怪的攻击是ai，血量是bi。我们约定Boss的攻击是am+1, 血量是bm+1
输出格式
每组数据输出一行，表示你能活着走出地牢的
最少初始血量 B。
最少初始血量 B。
输入样例 复制
1
3 2 1
T..
.S#
.#!
1 1
1 1
1 10
输出样例 复制
5