1 km を 100 分で移動するアリが、大平原の始点から終点に移動しようとしています。ただし、$x$ 軸と $y$ 軸に平行に移動する必要があり、丘陵地では移動に時間がかかる場合があります。始点、終点、丘陵地、および各丘陵地で 1 km 移動する時間が与えられたとき、始点から終点への最短時間を求めてください。

丘陵地は辺が $x$ 軸と $y$ 軸に平行な長方形で、長方形ごとに 1 km の移動時間が与えられます。この時間は長方形の内部だけに適用され、辺には適用されません。異なる長方形は重なりません。始点、終点、および異なる長方形の頂点の $x$ 座標はすべて整数で互いに異なり、$y$ 座標についても同様です。始点と終点は常に長方形の外側にあります。

上図は km 単位の座標で、左下 $(0,1)$、右上 $(5,2)$、1 km あたり 200 分の長方形と、左下 $(4,3)$、右上 $(9,4)$、1 km あたり 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);

この関数は 1 回だけ呼ばれます。src と dst は始点と終点です。各長方形の左下の点は p1、右上の点は p2 に与えられます。与えられた値から src から dst への最短時間を求めて返してください。

実装の詳細

plain.cpp という名前のファイルを 1 つ提出し、次の関数を実装してください。

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$ 座標の単位は 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$：長方形内部で 1 km 移動する時間（分）。

付属の採点プログラムは、あなたの 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