题目背景

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

题目描述

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 君从出发到到达比赛会场所需时间的最小值。

10 10 1 3 10 1
3
1 3 5 6 4
5 5 7 10 1
7 1 10 5 9

50

4 3 2 1 4 3
3
1 1 4 2 0
1 1 2 2 3
2 2 4 3 3

6

提示

样例 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 完成