SP3465 DRIVE - Drive through MegaCity

未来的超级城市由一个矩形街道网格构成。每个交叉路口的坐标是整数格式的 $x$ 和 $y$。要从坐标为 $x_a, y_a$ 的交叉路口 $a$ 行驶到坐标为 $x_b, y_b$ 的交叉路口 $b$，需要走 $|x_a - x_b| + |y_a - y_b|$ 个街区。通常，每走一个街区需要花费 10 个时间单位，因此可以轻松计算出从 $a$ 到 $b$ 的时间。然而，由于城市交通拥堵，估算最短行驶时间变得复杂，因此需要你来解决这个问题。 交通拥堵区域是由其左下角和右上角坐标定义的矩形区域。在这种拥堵区域内行驶一个街区的时间是已知的。在矩形区域内的所有街道受交通拥堵影响。有时候，绕过这些拥堵区域反而更省时间，而有时候则需要穿过其中一些，如示例中所示——在没有交通拥堵的地方行驶 17 个街区，每个街区花费 10 个时间单位；在轻微交通拥堵的地方行驶 2 个街区，每个街区花费 11 个时间单位。

输入包含多组测试数据。第一行是测试数据的数量。对于每组测试数据： 第一行提供四个整数 $x_a, y_a, x_b, y_b$，表示起点和终点的坐标。第二行是一个整数 $n$（$0 \leq n \leq 1000$），表示交通拥堵的数量。接下来的 $n$ 行描述各个交通拥堵区域。每个区域用五个整数 $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ 和 $t_i$ 来表示，前四个数表示拥堵区域的左下角和右上角坐标（$x_{1,i} < x_{2,i}$，$y_{1,i} < y_{2,i}$），$t_i$（$10 < t_i \leq 10^8$）是该区域内行驶一个街区所需的时间。所有坐标范围都是从 $0$ 到 $10^8$。各拥堵区域之间既不相交也不接触。起点和终点不位于任何交通拥堵区域的内部或边界上。

对于每组测试数据： 输出一个整数，表示从交叉路口 $a$ 到 $b$ 的最短行驶时间。 **本翻译由 AI 自动生成**