Description

在道路交叉口，通常会有交通信号灯指示行人（步行的人）何时可以过马路。一位聪明的行人可能会根据信号灯变绿的时间来优化她穿越城市的路线。

本题中的城市是一张网格，高 $N$ 行、宽 $M$ 列。我们的行人希望从西南角的东北顶点出发，前往东北角的西南顶点。你的目标是帮助她用尽可能快的方式，从一个角落到另一个角落。

行人可以在信号灯全程为绿灯时横穿马路，每次穿越用时 $1$ 分钟。行人也可以沿着一个街区的边，从一条街道走到另一条街道，这样的移动需要 $2$ 分钟。行人只能沿着街区的边移动，不能从一个街区的角直接斜向穿越到对角线的角。

交通信号灯的变换模式如下：在第 $i$ 个路口，南北方向的信号灯会保持绿灯 $S_i$ 分钟，此时东西方向为红灯。然后南北方向变为红灯，东西方向变为绿灯，持续 $W_i$ 分钟。之后，信号灯再次开始同样的循环。行人在 $t=0$ 分钟时开始移动；第 $i$ 个路口的信号灯在 $t=T_i$ 分钟时以南北方向绿灯开始一个循环。$t=T_i$ 之前也有信号灯的循环。

例如，编号为 0 的路口可能有以下数值：

$S_0 = 3$，$W_0 = 2$，$T_0 = 0$

南北方向在 0 分钟后变为绿灯，持续 $3$ 分钟，在此期间行人可以南北方向过马路，东西方向为红灯。然后信号灯切换，接下来的 $2$ 分钟行人可以东西方向过马路，南北方向为红灯。然后，信号灯在 $5$ 分钟后重新开始循环。这与如下配置完全等价：

$S_0 = 3$，$W_0 = 2$，$T_0 = 10$

Input Format

输入的第一行包含测试用例数 $C$。接下来是 $C$ 组测试数据，每组格式如下：

第一行包含 "N M"，分别表示水平方向道路（行）数 $N$ 和垂直方向道路（列）数 $M$。接下来 $N$ 行，每行描述该行上的所有路口信息，第 $i$ 行（$i$ 从 $0$ 开始，最北为 $0$ 行）包含 $3M$ 个整数，依次为：

$S_{i,0}$ $W_{i,0}$ $T_{i,0}$ $S_{i,1}$ $W_{i,1}$ $T_{i,1}$ $\dots$ $S_{i,M-1}$ $W_{i,M-1}$ $T_{i,M-1}$

$S_{i,j}$、$W_{i,j}$ 和 $T_{i,j}$ 分别表示从北到南第 $i$ 行、从西到东第 $j$ 列的路口的信号灯参数。

Output Format

对于每组测试数据，输出一行 "Case #x: t"，其中 $x$ 是测试编号，$t$ 是行人从西南角到东北角所需的最短时间（分钟数）。

2
1 1
3 2 10
1 2
1 5 3 1 5 2

Case #1: 4
Case #2: 7

Hint

样例说明

第一个样例如上所述。行人先向北穿越（$1$ 分钟），等待 $2$ 分钟后再向东穿越（$1$ 分钟），总共 $4$ 分钟。

第二个样例见下图。行人先向东穿越（$1$ 分钟），等待 $2$ 分钟后再向北穿越（$1$ 分钟），然后向东走一个街区（$2$ 分钟），再向东穿越（$1$ 分钟），总共 $7$ 分钟。

限制条件

• $C$、$N$、$M$、$S_{i,j}$、$W_{i,j}$、$T_{i,j}$ 均为非负整数。
• $C \leq 100$

小数据集（13 分）

• $1 \leq N, M \leq 3$
• $0 < S_{i,j}, W_{i,j} \leq 10$
• $0 \leq T_{i,j} \leq 20$

大数据集（20 分）

• $1 \leq N, M \leq 20$
• $0 < S_{i,j}, W_{i,j} \leq 10^7$
• $0 \leq T_{i,j} \leq 10^8$

翻译由 ChatGPT-4.1 完成。