U94308.Temporal Labyrinth

$HQ$被困在一个‌四维时空迷宫‌（Four-dimensional Temporal Labyrinth）中。迷宫是一个 $N × N$ 的二维网格，每个格子 ( $i$ , $j$ ) 有一个‌时间戳‌ t[i][j]，表示进入该格子的‌最小允许时间‌（单位：秒）。$HQ$从起点 ($0, 0$) 出发，目标是到达终点 ($N-1, N-1$)
$HQ$每秒可以向‌上下左右‌四个方向移动一格（不能斜走）。但迷宫中存在‌时空裂隙‌（Temporal Rifts）——这些是特殊的格子，当$HQ$进入时，会触发一个‌时间跳跃‌：
每个时空裂隙格子有一个‌跳跃参数‌ $k$（整数，可正可负）
当$HQ$进入一个裂隙格子时，‌当前时间会立即增加 $k$‌（即 current_time += k），然后$HQ$才被“传送”到该格子
时间跳跃‌可能让$HQ$回到过去‌（$k < 0$），也可能让$HQ$跳到未来（$k > 0$）
‌注意‌：即使$HQ$跳回过去，$HQ$‌仍然必须满足每个格子的最小时间戳约束‌。也就是说，进入格子 ( $i$ , $j$ ) 时，‌当前时间必须 $≥ t[i][j]$‌，否则$HQ$不能进入
此外，迷宫中还有‌时间锁‌（Time Locks）：
某些格子（非起点终点）是‌时间锁格子‌，$HQ$只能在特定时间点‌进入
每个时间锁格子 ( $i$ , $j$ ) 有一个‌唯一允许时间‌ lock_time[i][j]。
如果$HQ$到达该格子时，当前时间 $≠$ lock_time[i][j]，$HQ$‌不能进入‌，必须等待（但等待不消耗时间，$HQ$只能在时间匹配时才可进入）
$HQ$不能在格子上停留‌，必须在每一秒移动一次
求从 (0, 0) 到 (N-1, N-1) 的‌最短时间‌（即从出发到抵达终点所经历的总秒数），如果无法到达，输出 -1。

第一行一个数 $T$，表示每个平行宇宙里$HQ$被困的迷宫数
接下来共 $T$ 个测试数据，每个数据的格式如下：
第一行：$N$
接下来 $N$ 行，每行 $N$ 个整数，表示 t[i][j]（最小时间戳）
再接下来 $N$ 行，每行 $N$ 个整数，表示 rift[i][j]（裂隙跳跃值，若非裂隙则为 $0$）
再接下来 $N$ 行，每行 $N$ 个整数，表示 lock[i][j]（时间锁时间，若非锁则为 -1）

每个平行宇宙中$HQ$到达终点(N-1,N-1)的所需时间，若无法到达输出-1

$1 \le T \le 10,2 ≤ N ≤ 8,0 ≤ t[i][j] ≤ 100,-20 ≤ rift[i][j] ≤ 20,-1 ≤lock[i[j]≤150$，若为 -1 表示非锁
起点 (0,0) 和终点 (N-1,N-1) ‌不会是时间锁‌，但‌可以是裂隙‌
初始时间为 0，在第 0 秒位于 (0,0)
$HQ$必须在每一秒移动‌，不能原地等待（但时间跳跃会改变时间，从而可能让$HQ$“等待”到匹配的锁时间）