Obstacle Course

You have a puck that can slide across the ice. Once per second you may tap the puck from one side — north, south, east, or west. A tap changes the puck's velocity by 1 m/s in the direction it is pushed (a tap from the west pushes the puck toward the east). At the start the puck sits at $(0, 0)$ and is stationary.

Example of motion: suppose we tap the puck 5 times — from the west, from the south, from the west again, then twice from the north. During the 1st second the puck moves 1 m east and reaches $(1, 0)$. During the 2nd second it moves 1 m east and 1 m north, reaching $(2, 1)$. During the 3rd second it moves 2 m east and 1 m north, reaching $(4, 2)$. During the 4th second it moves 2 m east, reaching $(6, 2)$. During the 5th second it moves 2 m east and 1 m south, reaching $(8, 1)$.

Each second the puck travels in a straight line, directly from that second's start point to its end point. You do not have to tap the puck; if you don't, its direction and speed stay the same. The puck's maximum speed is 7 m/s along the east–west axis and 7 m/s along the north–south axis. For instance, if the puck is already moving 7 m/s west and 4 m/s north, it can no longer be tapped from the east, but it can still be tapped from the other directions.

Obstacles are also placed on the ice. Each obstacle is a stick lying flat on the ice, connecting two points with integer coordinates; every stick is oriented either north–south or east–west.

The goal is to move the puck to a given target point as quickly as possible without touching any obstacle. For simplicity, assume that both the sticks and the puck are one-dimensional, and that they touch each other if and only if they occupy exactly the same point. The puck is said to touch an obstacle if it finishes a second's path at a point occupied by an obstacle, or if it passes through such a point along the way.

The puck does not have to stop at the target point, but it must finish that second's path exactly at the target point.

The first line contains 3 integers: the integer coordinates of the target point, followed by the number of obstacles $N$ (at most 100). Each of the next $N$ lines contains four integers giving the coordinates of the start and end points of one obstacle stick. All input coordinates are integers in the range $-10 \ldots 10$.

Print exactly one integer: the minimum number of seconds in which the target can be reached. If the target cannot be reached, print $-1$.

For the configuration above, one optimal solution taps from the east, the south, the west, the west, and the south.