解题思路

1. 模型转换 将平面连续格网离散化，只关心所有矩形边界以及起、终点的横纵坐标。

2. 坐标压缩与节点构造

   • 收集所有矩形的 $X_{1,i},X_{2,i}$ 以及起点、终点的 $x$ 坐标，共计 $M_x$ 个不同值；同理收集所有 $Y_{1,i},Y_{2,i}$ 及起终点的 $y$ 坐标，共计 $M_y$。
   • 构造所有可能的“重要”交叉点 $P=(x_j,y_k)$，其中 $x_j$ 取自上述压缩后横坐标集合，$y_k$ 取自纵坐标集合。

题目内容

小钉生活在未来超级城市，未来超级城市是一个矩形街道网格。每个交叉点具有整数笛卡尔坐标 $x$ 和 $y$ 。从交叉点 $a$ (坐标 $xa,ya$ )到交叉点 $b$ (坐标北 $xb,yb$ )，你需要驾驶恰好 $|xa-xb| +|ya-yb|$ 个街区。通常情况下，驾驶通过一个街区需要 $10$ 个时间单位，因此可以轻松计算从 $a$ 到 $b$ 所需的时间。然而，超级城市中通过交通拥堵使区域得最小行驶时间的估算变得复杂，需要你解决这个问题。

交通拥堵影响一个由左下角和右上角坐标定义的矩形区域。在该拥堵区域中，驾驶一个街区所需的时间由给定的拥堵时间决定。所有严格位于矩形区域内部的街道都会受到交通拥堵的影响。有时，绕开交通拥堵区域可以节省时间，而省时，如示例所示，穿过部分拥堵区域可能更优——例如，$17$ 个街区在非拥堵区域行驶(每个街区耗时 $10$ 个时间单位,大计需要 $170$ 时间单位)，而 $2$ 个街区在轻度拥堵区域行驶(每个街区耗时 $11$ 个时间单位，共计需要 $22$ 时间单位)。

输入描述

输入文件的第一行包含四个整数 $xa,ya,xb,yb$ ——分别表示起点和终点的坐标。

第二行包含一个整数 $n(0≤n≤1000)$ ，表示交通拥堵的数量。

接下来的 $n$ 行描述交通拥堵。每条拥堵区域由五个整数 $X[1,i],Y[1,i],X[2,i],Y[2,i],ti$ 定义：

• 前四个整数表示拥堵区域的左下角和右上角坐标(满足 $x1,i<x2,i,y1,i<y2,i$ ) 。

• $ti(10<ti≤10^8)$ 表示在该拥堵区域内驾驶一个街区所需的时间。

输入文件中所有坐标的范围为 $0$ 到 $10^8$ (含边界)交通拥堵区域之间互不相交且互不接触。起点和终点不同，且不位于任何拥堵区域的内部或边界上。

输出描述

输出文件中仅包含一个整数--从起点到终点的最小行驶时间。

样例1

输入

1 6 15 3
4
2 1 3 7 44
5 2 10 4 33
8 5 11 9 22
12 1 14 8 11

输出

192