Obstacle Course

You have a puck that slides freely on ice. Once every second you may flick the puck from one of its four sides — north, south, east, or west. A flick from a given side pushes the puck toward the opposite side, changing that component of its velocity by $1$ m/s. Use a coordinate system where east is the $+x$ direction and north is the $+y$ direction, so a flick from the west increases the eastward velocity, a flick from the south increases the northward velocity, and so on. At the start the puck is at $(0,0)$ and is at rest.

Movement example. Suppose we flick the puck $5$ times: from the west, from the south, from the west again, and then twice from the north.

• During second $1$ the puck moves $1$ m east and reaches $(1,0)$.
• During second $2$ it moves $1$ m east and $1$ m north, reaching $(2,1)$.
• During second $3$ it moves $2$ m east and $1$ m north, reaching $(4,2)$.
• During second $4$ it moves $2$ m east, reaching $(6,2)$.
• During second $5$ it moves $2$ m east and $1$ m south, reaching $(8,1)$.

Each second the puck travels in a straight line, directly from its starting point to its ending point for that second. You are not required to flick; if you do not, the puck keeps the same direction and speed. The 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 currently moving $7$ m/s west and $4$ m/s north, it can no longer be flicked from the east (that would push it past $7$ m/s west), but it can still be flicked from the other sides.

Obstacles are also placed on the ice. Each obstacle is a stick lying flat that connects two points with integer coordinates. Your goal is to move the puck to a given target point as quickly as possible without touching any obstacle. For simplicity, both the sticks and the puck are one-dimensional, and they touch if and only if they occupy exactly the same point. The puck touches an obstacle if it finishes a second's path at a point occupied by an obstacle, or if it passes through such a point on the way.

The puck does not have to come to rest at the target, but it must finish one of its one-second straight-line moves exactly at the target point.

The first line contains $3$ integers: the coordinates of the target point ($x$ then $y$) and the number of obstacles $N$ (at most $100$). Each of the next $N$ lines contains four integers, the coordinates of the two endpoints of one obstacle stick. Every input coordinate is an integer in the range $-10 \ldots 10$.

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

One optimal solution for the illustrated case flicks the puck from these sides in order: east, south, west, west, south.