小红勇闯地下城
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红被传送到了一个地下城,地下城有nm列的,共n*m个房间。其中有一些房间有怪物。
小红初始有h血量,当她遭遇到一个战斗力为x的怪物时,她会消耗x的血量然后击杀这个怪物。小红想知道,自己能否找到一条路径成功安全到达终点?
我们认为,如果小红到达终点时的血量为正,则安全到达终点。血量小于等于 0 时死亡。
小红在迷宫中只能上下左右移动到相邻房间。

输入描述:

第一行输入一个正整数q,代表询问次数。
接下来共有q次询问:
每次询问,首先第一行输入三个正整数n,m,h,代表迷宫的行数、列数,以及小红初始的血量。
接下来的n行,每行输入一个长度为m的字符串。字符串仅包含数字字符('0'~'9')、'S'和'T'。其中数字代表房间里怪物的血量('0'代表该房间没有怪物),'S'代表小红的起点,'T'代表小红的终点。
我们默认,起点和终点是没有怪物的。
保证所有询问n*m的和不超过10^5
1\leq h \leq 10^9

输出描述:

对于每次询问输出一行答案:
如果小红能安全到达终点,则输出"Yes"。否则输出"No"。
示例1

输入

复制
2
3 3 3
S01
292
20T
2 2 1
4S
6T

输出

复制
No
Yes

说明

第一组询问,小红显然无法到达终点。
第二组询问,虽然小红初始只有 1 血量,但直接往下即可不遭遇怪物到达终点。