一隻在平地上每移動 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