Minimum Time to Reach the Guard Cell

Your mission is to help a team of robots navigate a grid-like facility to reach a strategic guard cell before the guard arrives. You are given a matrix where each cell contains the time required to traverse that cell. The robot always starts from the top-left corner (cell (1,1)). A target cell is provided along with a threshold time, \(T_g\) (in units of time), by which the guard is stationed. Using Dijkstra’s algorithm, determine the minimum time required for the robot to reach the guard cell. If the robot can arrive in strictly less time than \(T_g\), print the minimum time; otherwise, print SAFE.

Note: The guard cell coordinates are provided in 1-indexed format.

inputFormat

The input begins with an integer (T), the number of test cases. For each test case:

• The first line contains two integers (M) and (N) representing the number of rows and columns of the grid.
• The next (M) lines each contain (N) space-separated integers indicating the time cost for each cell.
• The subsequent line contains three integers: (target_x), (target_y), and (guard_time), where (target_x) and (target_y) are the 1-indexed coordinates of the guard cell and (guard_time) is the threshold time.

All input should be read from standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum time required to reach the guard cell if it is strictly less than the given guard time; otherwise, output SAFE. The result for each test case should be printed on its own line to standard output (stdout).## sample

1
3 5
5 3 8 2 6
1 4 7 8 2
3 6 5 9 1
2 4 20

SAFE