장애물 코스

빙판 위를 자유롭게 미끄러지는 퍽(litter)이 하나 있습니다. 매 초마다 퍽을 네 방향(북, 남, 동, 서) 중 한쪽에서 한 번 칠 수 있습니다. 어느 방향에서 치면 퍽은 그 반대쪽으로 밀려서, 해당 축의 속도가 $1$ m/s만큼 바뀝니다. 동쪽을 $+x$, 북쪽을 $+y$ 방향으로 두면, 서쪽에서 치면 동쪽 방향 속도가 늘고, 남쪽에서 치면 북쪽 방향 속도가 늘어나는 식입니다. 처음에 퍽은 $(0,0)$에 정지해 있습니다.

이동 예시. 퍽을 $5$번 친다고 합시다: 서쪽, 남쪽, 다시 서쪽, 그리고 북쪽에서 두 번.

• $1$초 동안 퍽은 동쪽으로 $1$ m 이동해 $(1,0)$에 도달합니다.
• $2$초 동안 동쪽으로 $1$ m, 북쪽으로 $1$ m 이동해 $(2,1)$에 도달합니다.
• $3$초 동안 동쪽으로 $2$ m, 북쪽으로 $1$ m 이동해 $(4,2)$에 도달합니다.
• $4$초 동안 동쪽으로 $2$ m 이동해 $(6,2)$에 도달합니다.
• $5$초 동안 동쪽으로 $2$ m, 남쪽으로 $1$ m 이동해 $(8,1)$에 도달합니다.

매 초 퍽은 그 초의 시작점에서 끝점까지 직선으로 이동합니다. 반드시 쳐야 하는 것은 아니며, 치지 않으면 방향과 속력이 그대로 유지됩니다. 속력의 최댓값은 동서 방향으로 $7$ m/s, 남북 방향으로 $7$ m/s입니다. 예를 들어 퍽이 지금 서쪽으로 $7$ m/s, 북쪽으로 $4$ m/s로 움직이고 있다면 동쪽에서는 더 이상 칠 수 없지만(서쪽 속력이 $7$ m/s를 넘게 되므로), 다른 방향에서는 칠 수 있습니다.

빙판에는 장애물도 놓여 있습니다. 각 장애물은 정수 좌표의 두 점을 잇는, 바닥에 놓인 막대입니다. 목표는 어떤 장애물도 건드리지 않고 퍽을 주어진 목표점까지 최대한 빠르게 옮기는 것입니다. 단순화를 위해 막대와 퍽은 모두 $1$차원이며, 정확히 같은 점에 있을 때에만 서로 닿는 것으로 봅니다. 퍽이 어떤 초의 경로를 장애물이 있는 점에서 끝내거나, 이동 중에 그런 점을 지나가면 장애물을 건드린 것입니다.

퍽이 목표점에서 멈출 필요는 없지만, 어떤 $1$초 직선 이동을 정확히 목표점에서 끝내야 합니다.

첫째 줄에 정수 $3$개가 주어집니다: 목표점의 좌표($x$ 다음 $y$)와 장애물의 개수 $N$(최대 $100$). 다음 $N$개의 줄에는 각각 정수 $4$개가 주어지며, 한 장애물 막대의 두 끝점 좌표를 나타냅니다. 입력의 모든 좌표는 $-10 \ldots 10$ 범위의 정수입니다.

정수 하나만 출력합니다: 목표점에 도달하는 데 필요한 최소 초 수. 도달할 수 없으면 $-1$을 출력합니다.

그림의 예시에 대한 한 가지 최적 해는 다음 순서로 퍽을 칩니다: 동쪽, 남쪽, 서쪽, 서쪽, 남쪽.