题目描述

探险者被困在一个神秘的网格世界，需要从 左上角 走到 右下角 才能逃脱。

网格的每个格子都有一个能量值，可能是正数、负数或零。

探险者拥有初始能量 $E$，当踏入一个格子时（包括起点），该格子的能量值会立即加到当前能量中。

在任何时刻，探险者的能量必须严格大于 $0$，否则会力竭而亡。

移动过程中不允许重复访问同一个格子。

请判断是否存在一条从起点到终点的路径，使得探险者能够存活到达终点。

输入格式

第一行一个整数 $t$，表示测试用例的个数。

对于每个测试用例：

• 第一行包含三个整数 $m, n, E$，分别表示网格的行数、列数和初始能量。
• 接下来 $m$ 行，每行 $n$ 个整数，表示对应格子的能量值 $a_{i,j}$。

输出格式

对于每个测试用例，输出一行：

• 若存在符合条件的路径，输出 YES；
• 否则输出 NO。

样例

2
2 3 3
-1 -2 2
2 1 -1
3 3 1
0 -1 1
-1 3 -1
1 -1 1

YES
NO

1
2 2 2
0 0
-2 0

YES

1
2 3 4
-3 0 -3
1 0 -1

YES

样例解释

第一组：网格大小为 $2 \times 3$，初始能量 $E=3$。

一种可行路径：

• 起点 $(0,0)$，能量变为 $3 + (-1) = 2$；
• 向下移动到 $(1,0)$，能量变为 $2 + 2 = 4$；
• 向右移动到 $(1,1)$，能量变为 $4 + 1 = 5$；
• 向右移动到 $(1,2)$ 终点，能量变为 $5 + (-1) = 4 > 0$。

成功逃脱，输出 YES。

第二组：网格大小为 $3 \times 3$，初始能量 $E=1$。

无论哪条路径，都会在到达终点前或到达时能量耗尽。输出 NO。

数据范围

对于 $100\%$ 的数据，$1 \le t \le 10$，$1 \le m, n \le 5$，$0 \le E \le 10^5$，$-10^3 \le a_{i,j} \le 10^3$。