一只蚂蚁以每 100 分钟 1km 的速度在平原上从起点移动到终点。蚂蚁必须沿平行于 $x$ 轴和 $y$ 轴的方向移动，且在丘陵地带移动时间可能会增加。给定起点、终点、各个丘陵地带的位置以及每个丘陵地带每移动 1km 所需的时间，请计算蚂蚁从起点到终点的最短移动时间。

丘陵地带为边平行于 $x$ 轴和 $y$ 轴的矩形，每个矩形给出了每移动 1km 所需的时间。该移动时间仅适用于矩形内部，不适用于边界。此外，任意两个矩形互不重叠，且起点、终点以及所有矩形的顶点 $x$ 坐标均为整数且互不相同。$y$ 坐标同样均为整数且互不相同。起点和终点始终位于所有矩形的外部。

下图展示了坐标单位为 km 的示例，其中一个矩形（左下角坐标 $(0,1)$，右上角坐标 $(5,2)$）每 km 移动时间为 200 分钟，另一个矩形（左下角坐标 $(4,3)$，右上角坐标 $(9,4)$）每 km 移动时间为 1,000 分钟。图中显示了起点为 A、终点为 B，以及起点为 C、终点为 D 时的最短时间路径，最短时间分别为 700 分钟和 1,000 分钟。

你需要实现以下函数：

long long shortest_path(pair<int, int> src, pair<int, int> dst, vector<pair<int, int>> p1, vector<pair<int, int>> p2, vector<int> w);

这是一个仅会被调用一次的函数。src 和 dst 分别为起点和终点。每个矩形的左下角坐标在 p1 中给出，右上角坐标在 p2 中给出。请利用给定的值计算并返回从 src 到 dst 的最短时间。

实现细节

你需要提交一个名为 plain.cpp 的文件，该文件中必须实现上述函数。该函数应按上述说明运行。当然，你可以创建其他函数并在内部使用。提交的代码不得执行任何输入输出操作或访问其他文件。

输入格式

提供的 grader 按以下格式读取输入。$x, y$ 坐标的单位为 km。

• 第 1 行：$N \ x_s \ y_s \ x_e \ y_e$
  • $N$：矩形的数量
  • $x_s, y_s$：起点的 $x, y$ 坐标
  • $x_e, y_e$：终点的 $x, y$ 坐标
• 接下来的 $N$ 行，每行包含：$x_1 \ y_1 \ x_2 \ y_2 \ w$
  • $x_1, y_1$：矩形左下角顶点的 $x, y$ 坐标
  • $x_2, y_2$：矩形右上角顶点的 $x, y$ 坐标
  • $x_1 < x_2$
  • $y_1 < y_2$
  • $w$：矩形内部每 1km 的移动时间（分钟）

提供的 grader 会输出你的代码在 shortest_path() 函数中返回的值。

数据范围

• $1 \le N \le 100,000$
• $100 \le w \le 10^8$
• $0 \le x, y \le 10^8$（$x, y$ 为起点、终点或矩形顶点的坐标值）
• $N, w, x, y$ 均为整数

子任务

• 子任务 1 [23 分]：$N \le 500$
• 子任务 2 [35 分]：$N \le 5,000$
• 子任务 3 [31 分]：$x_2 - x_1 = 1$
• 子任务 4 [61 分]：无额外限制

样例

输入 1

3 2 14 5 1
4 6 6 10 1000
0 7 3 9 200
1 2 8 5 150

输出 1

1750

输入 2

13 0 38 100 25
1 39 2 46 190
9 78 10 80 230
20 42 21 89 170
27 26 28 68 170
35 41 36 99 270
43 36 44 63 280
51 15 52 27 150
57 14 58 29 190
64 2 65 90 160
75 33 76 35 290
78 5 79 100 290
88 28 89 40 190
94 7 95 50 250

输出 2

11770