P14430 [JOISC 2013] 公交换乘 / Bus Tour

为了保证标程可以通过本题，本题内存限制翻倍。

JOI 市的公共交通系统十分发达。特别是，公交专用道路以网格状铺设，因此公交车不受交通状况影响，能够以恒定速度行驶。南北方向的公交专用道路有 $W$ 条，间隔为 $1$ km；东西方向的公交专用道路有 $H$ 条，间隔同样为 $1$ km。所有公交车均在矩形的运行路线上按顺时针方向以每分钟 $1$ km 的速度行驶。此外，在公交专用道路的交叉点设有公交车站。 JOI 君今天计划去观看一场板球比赛，但因睡过头而迟到了。虽然可能无法赶上比赛开始时间，但 JOI 君希望尽可能多地观看比赛，因此他想要尽早到达比赛场地。 ### 任务 JOI 君事先查好了公交车的运行信息，因此他知道每辆公交车的当前位置及其运行路线。请编写一个程序，计算从即刻出发，通过换乘公交车到达比赛场地所需的最短时间。假定移动仅使用公交车，且公交车之间的换乘需要时间：下车后不能立即在同一交叉点换乘同一时刻到达的公交车，只能换乘在下车后 **$1$ 分钟或更晚** 到达的公交车。此外，保证 JOI 君能够仅使用公交车到达比赛场地。

从标准输入读取以下输入数据： - 第 $1$ 行为 $6$ 个整数 $W, H, S_x, S_y, G_x, G_y$（$1 \leq S_x \leq W$，$1 \leq S_y \leq H$，$1 \leq G_x \leq W$，$1 \leq G_y \leq H$），以空格分隔。这表示有 $W$ 条南北方向的公交专用道路，以及与它们垂直的 $H$ 条东西方向的公交专用道路。此外，JOI 君初始位于从西数第 $S_x$ 条公交专用道路与从北数第 $S_y$ 条公交专用道路的交叉点；JOI 君的目的地（比赛会场）位于从西数第 $G_x$ 条公交专用道路与从北数第 $G_y$ 条公交专用道路的交叉点。JOI 君的初始位置与目的地不同，且 JOI 君出发瞬间其初始位置没有公交车。 - 第 $2$ 行为一个整数 $N$，表示 JOI 市运行的公交车数量。 - 后续 $N$ 行描述公交车信息。第 $i$ 行包含 $5$ 个整数 $X_{1i}, Y_{1i}, X_{2i}, Y_{2i}, T_i$（$1 \leq X_{1i} < X_{2i} \leq W$，$1 \leq Y_{1i} \leq Y_{2i} \leq H$，$0 \leq T < 2 \times (X_{2i} - X_{1i} + Y_{2i} - Y_{1i})$）。这表示第 $i$ 辆公交车的路线西北端位于从西数第 $X_{1i}$ 条公交专用道路与从北数第 $Y_{1i}$ 条公交专用道路的交叉点，路线东南端位于从西数第 $X_{2i}$ 条公交专用道路与从北数第 $Y_{2i}$ 条公交专用道路的交叉点。此外，在 JOI 君出发时刻，第 $i$ 辆公交车位于从路线西北端顺时针前进 $T_i$ km 的位置。

输出一行，表示 JOI 君从出发到到达比赛会场所需时间的最小值。

### 样例 1 解释 :::align{center}  ::: 上图是从空中俯瞰该输入示例中 JOI 市的示意图。圆形标记表示公交车的当前位置。箭头表示该公交车的行驶路线。JOI 君的当前位置用三角形标示，目的地比赛会场用四边形标示。 JOI 君必须等待 1 号公交车到来。假设他在 $10$ 分钟后搭乘 1 号公交车，则 $11$ 分钟后的状态如下所示。 :::align{center}  ::: 接着，JOI 君需要从 1 号公交车换乘至 2 号公交车。假设他在出发后 $16$ 分钟下车，则 $19$ 分钟后的状态如下所示。 :::align{center}  ::: 搭乘 2 号公交车后，需换乘至 3 号公交车。出发后 $29$ 分钟，当 JOI 君从 2 号公交车下车时，同一交叉点正停靠着 3 号公交车。然而，换乘需要 $1$ 分钟时间，因此无法搭乘这班公交车。 假设 JOI 君在出发后 $43$ 分钟搭乘 3 号公交车，则到达比赛会场前 $49$ 分钟的场景如下所示。 :::align{center}  ::: $1$ 分钟后，JOI 君抵达比赛会场。由于无法比这更早到达，程序应输出 $50$。 ### 限制 所有输入数据满足以下条件： - $2 \leq W \leq 1000$ - $2 \leq H \leq 1000$ - $1 \leq N \leq 1000$ ### 子任务 #### 子任务 1 [30 分] 满足以下条件： - $W \leq 30$ - $H \leq 30$ - $N \leq 30$ #### 子任务 2 [50 分] 满足以下条件： - $W \leq 300$ - $H \leq 300$ - $N \leq 300$ #### 子任务 3 [20 分] 无额外限制。 翻译由 DeepSeek V3 完成