A freight yard is laid out on an infinite integer grid. A cart may walk directly between any two points (ax, ay) and (bx, by) at a cost equal to their Manhattan distance, |ax - bx| + |ay - by|, in any of the four axis directions, any number of times.

The yard also has k one-way conveyor belts. The i-th conveyor is described by five integers x1_i, y1_i, x2_i, y2_i, cost_i: stepping onto the conveyor at (x1_i, y1_i) carries the cart all the way to (x2_i, y2_i) for a flat fee of cost_i, regardless of how far apart those two points are and regardless of the Manhattan distance between them (a conveyor may in fact be a bad deal if its fee exceeds the Manhattan distance it spans, in which case simply walking past it is better). Conveyors only run in the stated direction; there is no belt running from (x2_i, y2_i) back to (x1_i, y1_i) unless a separate conveyor says so.

Given a start point (sx, sy) and a target point (tx, ty), find the minimum total cost for the cart to travel from the start to the target, using any combination of walking and riding conveyors (each conveyor may be used, skipped, or in principle ridden more than once, in whatever order gets the cart to the target most cheaply).

Input format

Line 1: four integers sx sy tx ty. Line 2: one integer k, the number of conveyor belts. Each of the next k lines: five integers x1 y1 x2 y2 cost describing one conveyor.

Output format

A single integer: the minimum total travel cost from (sx, sy) to (tx, ty).

Constraints

• 1 <= sx, sy, tx, ty <= 10^5
• 0 <= k <= 200
• 1 <= x1, y1, x2, y2 <= 10^5 for every conveyor
• 1 <= cost <= 10^5 for every conveyor

1 1 10 10
1
3 3 8 8 5

13

2 3 7 9
0

11