장애물 코스

얼음 위를 미끄러질 수 있는 퍽(원반)이 하나 있습니다. 1초에 한 번, 퍽을 북·남·동·서 중 한쪽에서 툭 칠 수 있습니다. 한 번 치면 퍽이 밀려나는 방향의 속도가 초당 1미터만큼 커집니다(서쪽에서 치면 퍽은 동쪽으로 밀립니다). 처음에 퍽은 $(0, 0)$에 정지해 있습니다.

움직임 예시: 퍽을 서쪽, 남쪽, 다시 서쪽, 그다음 북쪽에서 두 번, 이렇게 총 5번 친다고 합시다. 1초 동안 퍽은 동쪽으로 1미터 이동해 $(1, 0)$에 도달합니다. 2초 동안에는 동쪽으로 1미터, 북쪽으로 1미터 이동해 $(2, 1)$에 도달합니다. 3초 동안에는 동쪽으로 2미터, 북쪽으로 1미터 이동해 $(4, 2)$에 도달합니다. 4초 동안에는 동쪽으로 2미터 이동해 $(6, 2)$에 도달합니다. 5초 동안에는 동쪽으로 2미터, 남쪽으로 1미터 이동해 $(8, 1)$에 도달합니다.

매 초마다 퍽은 그 초의 시작점에서 끝점까지 직선으로 움직입니다. 퍽을 꼭 칠 필요는 없으며, 치지 않으면 방향과 속도가 그대로 유지됩니다. 퍽의 최대 속도는 동서 방향으로 7 m/s, 남북 방향으로 7 m/s입니다. 예를 들어 퍽이 이미 서쪽으로 7 m/s, 북쪽으로 4 m/s로 움직이고 있다면, 더 이상 동쪽에서는 칠 수 없지만 다른 방향에서는 칠 수 있습니다.

얼음 위에는 장애물도 놓여 있습니다. 각 장애물은 얼음 위에 눕혀 놓인 막대기로, 정수 좌표를 가진 두 점을 잇습니다. 모든 막대기는 남북 방향 또는 동서 방향으로 놓여 있습니다.

목표는 어떤 장애물도 건드리지 않고 퍽을 주어진 목표 지점까지 가능한 한 빨리 옮기는 것입니다. 단순화를 위해 막대기와 퍽은 모두 1차원(점)이라고 가정하며, 정확히 같은 점에 있을 때에만 서로 닿는 것으로 봅니다. 퍽이 어떤 초의 이동을 장애물이 있는 점에서 끝내거나 이동 도중 그런 점을 지나가면, 장애물을 건드린 것으로 간주합니다.

퍽이 목표 지점에서 반드시 멈춰 있을 필요는 없지만, 해당 초의 이동을 정확히 목표 지점에서 끝내야 합니다.

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

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

위 그림의 배치에서, 한 가지 최적해는 동쪽, 남쪽, 서쪽, 서쪽, 남쪽 순서로 치는 것입니다.