一只在平地上每移动 1 千米需要 100 分钟的蚂蚁，想从大平原上的起点到达终点。它只能平行于 $x$ 轴和 $y$ 轴移动，在丘陵区域内移动所需的时间可能更长。给定起点、终点、各个丘陵区域，以及在每个丘陵区域内移动 1 千米所需的时间，求蚂蚁从起点到终点的最短时间。

丘陵区域是边平行于 $x$ 轴和 $y$ 轴的矩形，每个矩形给定移动 1 千米所需的时间。该时间仅适用于矩形内部，不适用于边界。不同矩形互不重叠。起点、终点以及不同矩形的顶点的 $x$ 坐标均为整数且互不相同，$y$ 坐标也同样均为整数且互不相同。起点和终点总在矩形外部。

上图坐标以千米为单位，展示了左下角为 $(0,1)$、右上角为 $(5,2)$、每千米耗时 200 分钟的矩形，以及左下角为 $(4,3)$、右上角为 $(9,4)$、每千米耗时 1000 分钟的矩形。图中标出了从 $A$ 到 $B$ 和从 $C$ 到 $D$ 的最短时间路径，最短时间分别为 700 分钟和 1000 分钟。

你必须实现以下函数。

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 的文件，其中需要实现以下函数。

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);

该函数的行为必须符合上述说明。你可以编写其他函数供内部使用。提交的代码不得进行输入输出，也不得访问其他文件。

评测程序示例

给定的评测程序按以下格式读取输入。$x$、$y$ 坐标值的单位为千米。

第一行：$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$：在矩形内部移动 1 千米所需的时间，单位为分钟。

给定的评测程序输出你的 shortest_path() 函数的返回值。

数据范围

• $1\le N\le100000$
• $100\le w\le10^8$
• $0\le x,y\le10^8$，其中 $x,y$ 为起点、终点或矩形顶点的坐标。
• $N,w,x,y$ 均为整数。

子任务

1. (23 分) $N\le500$
2. (35 分) $N\le5000$
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