You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在一个高度自动化的物流园区中，AGV（自动导引车）沿着铺设好的网格轨道运送货物。每段轨道都有固定的通行时间（边权）。AGV 遵循严格的运动规则：

• 它可以从静止状态启动，但启动后的第一段轨道需要额外的时间来加速（相当于通行时间加倍）。
• 它也可以随时减速停止，但停止前最后一段轨道也需要加倍的时间来减速。
• 如果 AGV 要改变方向，它必须先完全停止，再重新启动——这意味着转向会使得转向前的最后一段轨道和转向后的第一段轨道都加倍。

园区调度中心需要为 AGV 规划从起点到终点的最短时间路径，同时保证最终在终点完全停止。请你帮助计算这个最短时间。

题目描述

在一个 $R \times C$ 的方格图中，每个格子是一个结点，相邻格子之间由网格边相连，每条边有一个正权值 $w$（表示沿该边移动所需的时间）。
机器人从起点 $r_1, c_1$ 出发，要到达终点 $r_2, c_2$。机器人可以沿着网格线水平或垂直移动，移动速度恒定，因此经过一条边需要的时间等于该边的权值。

机器人具有以下行为规则：

• 机器人的初始速度为 0（静止在起点），最终到达终点时速度也必须为 0（静止在终点）。
• 机器人可以在移动过程中随时停止（即速度变为 0），也可以从静止状态开始沿某个方向移动。
• 如果机器人从静止状态开始移动，则它经过的第一条边的时间要加倍（即需要 $2w$ 时间）。
• 如果机器人从移动状态变为静止状态，则它经过的最后一条边的时间也要加倍（即需要 $2w$ 时间）。
• 如果机器人要改变方向（例如从向右变为向下），它必须先停下（使速度变为 0），然后再启动新方向的移动。因此，转向会使得转向前的最后一条边和转向后的第一条边的时间都加倍。
• 注意：如果一条边的两端速度都是 0（即机器人从静止出发，经过一条边后停在相邻格点），则该边的时间只加倍一次（即 $2w$）。

请计算机器人从起点到终点的最短时间。

输入格式

输入包含多组测试数据。每组数据的第一行包含六个整数 $R, C, r_1, c_1, r_2, c_2$，分别表示方格图的行数、列数、起点的行和列、终点的行和列。

接下来依次输入所有边的权值：

• 对于第 $i$ 行$1 \le i \le R$，先输入 $C-1$ 个整数，表示该行中从左到右的水平边的权值（即连接 $i, j$ 和 $i, j+1$ 的边）。
• 如果 $i < R$，则再输入 $C$ 个整数，表示第 $i$ 行中从上到下的垂直边的权值（即连接 $i, j$ 和 $i+1, j$的边）。

所有边权均为正整数。
输入以一行 0 0 0 0 0 0 结束（该行不需要处理）。

输出格式

对于每组测试数据，输出一行，格式为 Case X: ans，其中 X 是测试数据编号（从 1 开始），ans 是机器人从起点到终点的最短时间。如果无法到达，输出 Impossible。

输入输出样例 #1

输入 #1

2 2 1 1 2 2
10
20 30
40
0 0 0 0 0 0

输出 #1

Case 1: 80

说明/提示

样例解释

机器人从 (1,1) 静止出发，向右移动到 (1,2) 并静止，花费 $2 \times 10 = 20$；
然后从 (1,2) 静止出发，向下移动到 (2,2) 并静止，花费 $2 \times 30 = 60$；
总时间 $20+60=80$。

数据范围与约定

• $1 \le R, C \le 100$
• $1 \le r_1, r_2 \le R$，$1 \le c_1, c_2 \le C$
• 边权均为正整数，不超过 $10^4$
• 每组测试数据最多包含 $500$ 个格子
• 输入文件大小不超过 10 MB