암벽 등반
시간 제한2초메모리 제한128 MB
각 이동 시 x, y 차이가 2 이하인 홀드로만 옮길 수 있을 때, (0,0)에서 높이 y=T에 도달하는 최소 이동 횟수를 구하는 문제입니다.
문제
어떤 암벽에 홈 n개가 파여 있다. 각 홈은 좌표 (x, y)로 나타낸다. 현재 위치가 (x, y)일 때, 다른 홈 (a, b)로 이동하려면 |a - x| <= 2이고 |b - y| <= 2이어야 한다.
처음 위치는 (0, 0)이다. 홈들을 이용해 이동하면서 암벽의 정상인 높이 y = T에 도달하려고 한다. 정상에 도달했을 때의 x좌표는 상관없다. 이동 횟수를 최소로 할 때 필요한 이동 횟수를 구하라.
입력
첫째 줄에 홈의 개수 n과 목표 높이 T가 주어진다. (1 <= n <= 50,000, 1 <= T <= 200,000)
다음 n개의 줄에는 각 홈의 좌표 x, y가 주어진다. 두 좌표는 모두 0 이상이며, x <= 1,000,000, y <= T를 만족한다. 현재 위치인 (0, 0)은 입력으로 주어지지 않는다.
출력
첫째 줄에 정상까지 도달하는 최소 이동 횟수를 출력한다. 정상에 도달할 수 없으면 -1을 출력한다.