Fastest Grid Route

The first line contains four integers a b c d. (a, b) is the starting intersection and (c, d) is the destination; the two intersections are different.

The second line contains the number of shopping districts n, where 0 <= n <= 1000.

Each of the next n lines contains five integers lx ly hx hy t describing one shopping district. (lx, ly) is the bottom-left corner of the rectangle, (hx, hy) is the top-right corner, and t is the time needed to drive one block on roads inside it. 10 <= t <= 10^8, and every coordinate is an integer from 0 to 10^8, inclusive. No two shopping districts overlap or even touch at their boundaries.

Print the minimum travel time from the starting intersection to the destination.

A city has an infinite rectangular grid of horizontal and vertical roads. Each intersection is represented by integer coordinates (x, y). Usually, driving one block takes 10 units of time, so a shortest-distance route between (a, b) and (c, d) uses |a - c| + |b - d| blocks.

Some shopping districts are heavily congested. Each district is an axis-aligned rectangle, and every road segment lying completely inside that rectangle has its own one-block travel time. If a segment is not inside any shopping district, driving one block on it takes 10 units of time. Sometimes it is faster to go around a district; sometimes it is faster to pass through part of one.

In the illustration below, normal roads take 10 units per block, while districts A, B, C, and D take 44, 33, 22, and 11 units per block. The fastest route between (1, 6) and (15, 3) is the marked route: its length is 19 and its total time is 192. The fastest route that avoids all shopping districts has length 21 and total time 210.

Given two intersections, compute the minimum possible travel time between them.