27655번 - 점프

간단한 점프 게임이 있다. 캐릭터는 1층에 위치한 발판 중 하나를 골라 정수 위치에서 시작할 수 있다. 이 캐릭터는 2가지 액션 중 한 가지를 할 수 있으며, 게임의 목표는 가장 높은 발판에 최소한의 점프로 도착하는 것이다.

1. 현재 위치한 발판 위에서 위치가 정수가 되도록 자유롭게 움직인다. 즉, 좌/우로 1씩 움직일 수 있다.
2. 현재 위치한 발판에서 수직으로 점프한다. 이렇게 점프를 할 때 처음 만나게 되는 위치의 발판으로 이동한다. 즉, 현재 위치에서 위쪽으로 반직선을 그을 때 첫 교점이 생기는 발판으로 이동한다.

아래와 같은 예시를 생각해 보자.

1층에는 2개의 발판이 존재한다. 1층의 오른쪽 발판과 왼쪽 발판 중 어느 곳에서든 캐릭터는 시작할 수 있으며, 이 경우 오른쪽 발판에서 4층으로 1번의 점프로 이동하는 방법이 최적이다. 또한 점프 방식에 대한 정의에 의하여 1층의 오른쪽 발판 위에 캐릭터가 있고, 만약 위치 8에서 점프를 할 경우 2층의 발판에 도달함을 알 수 있다.

발판의 개수와 가장 높은 발판이 몇 층인지를 나타내는 정수 $N$과 $K$가 주어진다.

다음 줄부터 $N$개의 줄에 걸쳐 발판의 정보를 나타내는 정수 $L_i$, $R_i$, $K_i$가 주어진다. 이는 $i$번째 발판이 $L_i$에서 $R_i$까지의 구간으로 나타나며, $K_i$ 층에 위치하였음을 의미한다. 같은 층에 위치한 발판끼리 겹치는 경우는 없다. 1층과 $K$층에는 적어도 하나의 발판이 존재함이 보장된다.

1층의 임의의 발판에서 출발하여 $K$층의 임의의 발판에 도착하는 최소 점프 횟수를 출력한다. 만약 도달할 수 있는 방법이 없는 경우 -1을 출력한다.

• $1 \le{} N, K \le{} 300\,000$
• $1 \le{} L_i < R_i \le{} 10^9$, $1 \le{} K_i \le{} K$