An ant that travels $1\,\text{km}$ in $100$ minutes wants to move from a starting point to a destination on a Great Plain. However, it must move parallel to the $x$-axis and $y$-axis, and the travel time may increase in hilly areas. Given the starting point, the destination, the hilly areas, and the time it takes to travel $1\,\text{km}$ in each hilly area, calculate the fastest time for this ant to travel from the starting point to the destination.

Hilly areas are rectangular in shape, consisting of sides parallel to the $x$-axis and $y$-axis, and for each rectangle, the time taken to travel $1\,\text{km}$ is given. This travel time applies only to the interior of the rectangle and not to its boundaries. Furthermore, no two rectangles overlap, and the $x$-coordinates of the starting point, the destination, and the vertices of all different rectangles are all distinct integers. The same applies to the $y$-coordinates, which are all distinct integers. The starting point and the destination always exist outside the rectangles.

The example above shows a rectangle with a travel time of $200$ minutes per km (bottom-left coordinate $(0,1)$ and top-right coordinate $(5,2)$) and a rectangle with a travel time of $1,000$ minutes per km (bottom-left coordinate $(4,3)$ and top-right coordinate $(9,4)$) in km-unit coordinates. The shortest time paths are shown for the case where the starting point is $A$ and the destination is $B$, and for the case where the starting point is $C$ and the destination is $D$, with shortest times of $700$ minutes and $1,000$ minutes, respectively.

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 exactly once. src and dst are the starting point and the destination. The bottom-left point of each rectangle is given in p1 and the top-right point is given in p2. Use the given values to find and return the shortest time from src to dst.

Implementation Details

You must submit a single file named plain.cpp. This file must contain the implementation of 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 must operate as described above. You may create other functions to use internally. The submitted code must not perform any input/output operations or access other files.

Grader Example

The provided grader reads input in the following format. The unit for $x$ and $y$ coordinate values is km.

• Line 1: $N$ $x_s$ $y_s$ $x_e$ $y_e$
  • $N$: Number of rectangles
  • $x_s, y_s$: $x, y$ coordinates of the starting point
  • $x_e, y_e$: $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$: $x, y$ coordinates of the bottom-left vertex of the rectangle
  • $x_2, y_2$: $x, y$ coordinates of the top-right vertex of the rectangle
  • $x_1 < x_2$
  • $y_1 < y_2$
  • $w$: Time to travel $1\,\text{km}$ inside the rectangle (minutes)

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

Constraints

• $1 \le N \le 100,000$
• $100 \le w \le 10^8$
• $0 \le x, y \le 10^8$ ($x, y$ are coordinate values of the starting point, destination, or rectangle vertices)
• $N, w, x, y$ are all integers

Subtasks

• Subtask 1 [23 points]: $N \le 500$
• Subtask 2 [35 points]: $N \le 5,000$
• Subtask 3 [31 points]: $x_2 - x_1 = 1$
• Subtask 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

Figure 1. The example above shows a rectangle with a travel time of 200 minutes per km and a rectangle with a travel time of 1,000 minutes per km. The shortest time paths are shown for the case where the starting point is A and the destination is B, and for the case where the starting point is C and the destination is D.