시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 442 104 71 24.150%

문제

어떤 암벽에 n(1≤n≤50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a-x|≤2이고 |b-y|≤2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들일 이용하여 이동하면서 y=T(1≤T≤200,000)일 때까지, 즉 암벽의 정상까지 오르려고 한다.

현재 당신이 있는 위치는 (0, 0)이다. 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다. 정상에 오를 때의 x좌표는 아무 것이나 되어도 상관이 없다.

입력

첫째 줄에 n, T가 주어진다. 다음 n개의 줄에는 각 점의 x, y좌표가 주어진다. 두 좌표는 모두 0이상이며, x좌표는 1,000,000이하, y좌표는 T이하이다. 입력에 현재 위치인 (0, 0)은 주어지지 않는다.

출력

첫째 줄에 최소 이동 회수를 출력한다. 만약, 정상에 오를 수 없으면 -1을 출력한다.

예제 입력

5 3
1 2
6 3
4 1
3 2
0 2

예제 출력

4

힌트

출처

  • 문제를 번역한 사람: author10
  • 빠진 조건을 찾은 사람: Nada