Minimum Time in Wormhole Network

You will be given a starting point (sx, sy) and a destination point (dx, dy) in the two-dimensional coordinate system representing the universe.

Your spacecraft can move only in X(left or right) or Y(up or down) direction, and not in the diagonal direction. To go from one point (x1, y1) to another point (x2, y2), total time taken is |x2 - x1| + |y2 - y1| seconds.

Also, in this two-dimensional system, N wormholes are present. If you go through a wormhole, spacecraft will take some time to travel from the entry of the wormhole to its exit point. You have to find out the minimum time in which you can go from the source to the destination.

What is a Wormhole?

A wormhole is a sort of tunnel that joins distant points in space, or even two universes, via space-time curvature. Theoretically, such a tunnel could be traversed from one point in space to another without actually travelling the distance between them.

Note:

1. Endpoints of all the wormholes are pairwise distinct.
It means if a wormhole starts or ends at the coordinate (x, y) then no other wormhole will start or end from the same coordinate. This holds true for the source and the destination coordinates as well.

2. If your path intersects with the wormhole, your spacecraft won't get sucked into the wormhole.  As soon as you reach the entry/exit point of a wormhole you will come out from the exit/entry point( Wormholes are bi-directional).

Input format :

The first line contains 4 space-separated integers sx, sy, dx and dy where (sx, sy) is the source point and (dx, dy) is the destination point.

The second line contains an integer N representing the number of wormholes.

From the third line, N lines contain five space-separated integers where the first two integers represent the starting point of wormhole next two integers represent the exit point of the wormhole and the fifth integer represents the time taken if this wormhole is used.

Output format :

The only line of output print the minimum time in which you can travel from the source to the destination point.

Constraints :

1 <= Coordinates <= 10^5
1 <= N <= 200
1 <= Wormhole Time <= 10^5

Time Limit: 1 sec