캥거루 레오

마법사의 저주를 받은 캥거루 레오가 좁은 캐니언에서 정신을 차렸다. 눈앞에는 넘을 수 없는 벽이 서 있고, 근처에는 수천 년의 풍화로 깎여 나간 바위 기둥의 잔해가 흩어져 있다. 악의 힘이 레오에게서 걷는 능력과 방향을 바꾸는 능력을 빼앗았다. 그래도 옆으로는 뛸 수 있다! 이 생각은 동물다우면서도 매우 영리한 그의 머리에 떠올랐다. 용감한 레오는 두려움과 통증을 참고 탈출하기로 했다. 그의 임무는 세상 전체에 중요했다. 레오는 돌기둥 위로, 또는 돌기둥 사이로 좌우로만 뛰어서 캐니언의 끝에 도달해야 한다.

레오는 자신이 무엇을 할 수 있는지 알고 있었다. 그는 그저 캥거루일 뿐이고, 평범한 캥거루는 논리적으로 생각하거나 행동을 계획하지 못한다. 평범한 캥거루는... 절망에 빠져 무기력해진 그는 자신을 위대한 임무와 갈라놓은 철의 장막에서 틈을 찾아냈다. 그는 사람들을 떠올렸다...

레오는 서툰 앞발로 바늘을 제거한 선인장 껍질에 캐니언의 지도를 그렸다. 그 껍질을 바람에 날려 보내고, 누군가 메시지를 받아 도와주기를 기다리며 바랐다.

이 메시지가 당신에게 도착했다. 캥거루를 구해 주십시오!

메시지를 살펴본 당신은, 껍질에 그려진 것이 레오의 위치를 지나고 그가 움직일 수 있는 유일한 방향을 따라 자른 캐니언의 단면도라고 판단한다. 캐니언의 왼쪽과 오른쪽 가장자리는 높이가 같은 깎아지른 절벽이다. 캐니언 안에는 변이 바닥과 평행하거나 수직인 직사각형 단면의 돌기둥이 여러 개 서 있다. 가장자리의 높이와 각 기둥의 크기는 알려져 있다.

캐니언 안에서 레오는 점프로만 움직일 수 있다. 한 번의 점프 궤적은 세 구간으로 이루어진다. 현재 지점에서 높이 $p$까지 수직으로 올라가고, 왼쪽 또는 오른쪽으로 $q$만큼 수평으로 이동한 뒤, 그 지점에서 최대 $r$만큼 수직으로 내려온다. $p$, $q$, $r$은 자연수이며, $p$와 $q$의 합은 $n$이다. 점프 궤적의 어느 구간도 캐니언 안 기둥의 경계와 교차하거나 닿을 수 없다. 다음 점프는 착지한 지점에서 시작한다. 캐니언을 빠져나가려면 왼쪽 가장자리 왼쪽이나 오른쪽 가장자리 오른쪽 지점에 도달하면 된다.

첫 줄에는 공백으로 구분된 정수 여섯 개가 다음 순서로 주어진다. $A$, $B$, $H$, $n$, $r$, $m$이다. $-10\,000 \le A \le 0$과 $0 < B \le 10\,000$은 캐니언 왼쪽과 오른쪽 가장자리의 좌표이고, $0 \le H \le 1\,000$은 가장자리의 높이이다. $2 \le n \le 1\,000$은 점프의 처음 두 구간 길이의 합이고, $0 < r \le 1\,000$은 세 번째 구간 길이의 상한이다. $0 \le m < 20\,000$은 캐니언 안 기둥의 개수이다.

이어지는 $m$개 줄에는 $-10\,000 \le X_i < Y_i \le 10\,000$인 $i$번째 기둥의 왼쪽과 오른쪽 가장자리 좌표, 그리고 $0 \le Z_i \le 1\,000$인 기둥의 높이가 주어진다. 기둥끼리는 겹치지 않지만, 서로 또는 캐니언의 가장자리와 닿을 수는 있다.

캐니언을 빠져나가는 데 필요한 최소 점프 횟수를 정수 하나로 출력한다. 레오가 캐니언을 빠져나갈 수 없으면 0을 출력한다.

그림의 캥거루는 위로 2, 오른쪽으로 1씩 뛰는 점프를 4번 한다.