An ant that travels 1 km in 100 minutes wants to move from a starting point to a destination on a great plain. It must move parallel to the $x$- and $y$-axes, and travel may take longer in hilly areas. Given the start, destination, hilly areas, and the time to travel 1 km in each hilly area, calculate the minimum time for the ant to reach its destination.

Each hilly area is a rectangle whose sides are parallel to the $x$- and $y$-axes, with a specified travel time per kilometre. This time applies only in the rectangle’s interior, not on its boundary. No two rectangles overlap. The $x$-coordinates of the start, destination, and vertices of different rectangles are integers and do not coincide; the same holds for their $y$-coordinates. The start and destination are always outside the rectangles.

The figure above uses coordinates in kilometres. It shows a rectangle with lower-left corner $(0,1)$, upper-right corner $(5,2)$, and travel time 200 minutes per kilometre, and a rectangle with lower-left corner $(4,3)$, upper-right corner $(9,4)$, and travel time 1000 minutes per kilometre. The fastest routes from $A$ to $B$ and from $C$ to $D$ are shown; their minimum times are respectively 700 and 1000 minutes.

You must implement the following function.

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

This function is called only once. src and dst are the start and destination. Each rectangle’s lower-left corner is given in p1 and its upper-right corner in p2. Using the given values, return the minimum travel time from src to dst.

Implementation Details

You must submit one file named plain.cpp, implementing the following function.

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

The function must behave as described above. You may implement other functions for internal use. Your submitted code must not perform input/output or access other files.

Sample Grader

The provided grader reads input in the following format. The $x$- and $y$-coordinates are in kilometres.

First line: $N\ x_s\ y_s\ x_e\ y_e$.

• $N$: the number of rectangles.
• $x_s,y_s$: the $x,y$ coordinates of the start.
• $x_e,y_e$: the $x,y$ coordinates of the destination.

Each of the next $N$ lines: $x_1\ y_1\ x_2\ y_2\ w$.

• $x_1,y_1$: the $x,y$ coordinates of the rectangle’s lower-left corner.
• $x_2,y_2$: the $x,y$ coordinates of its upper-right corner.
• $x_1<x_2$.
• $y_1<y_2$.
• $w$: time in minutes to travel 1 km inside the rectangle.

The provided grader prints the value returned by your shortest_path() function.

Constraints

• $1\le N\le100000$
• $100\le w\le10^8$
• $0\le x,y\le10^8$, where $x,y$ are coordinates of the start, destination, or a rectangle vertex.
• $N,w,x,y$ are all integers.

Subtasks

1. (23 points) $N\le500$
2. (35 points) $N\le5000$
3. (31 points) $x_2-x_1=1$
4. (61 points) No additional constraints.

Examples

Input 1

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

Output 1

1750

Input 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

Output 2

11770