클라이밍 벽 오르기

박람회에서 가장 인기 있는 시설은 클라이밍 벽이다. 베시는 벽을 오를 경로를 미리 정해 두려고 한다.

벽은 너비가 30000밀리미터, 높이가 $H$ ($1001 \le H \le 30000$) 밀리미터이다. 벽에는 발굽 홀드가 $F$ ($1 \le F \le 10000$) 개 있고, 각 홀드의 위치는 밀리미터 단위 좌표 $(X, Y)$ 로 주어지며 같은 위치에 놓인 홀드는 없다. 좌표 $(0, 0)$ 은 벽 왼쪽 끝의 지면이다. 홀드가 너무 붙어 있으면 소가 디딜 수 없으므로, 서로 다른 두 홀드 사이의 거리는 항상 300밀리미터 이상이다. 꼭대기까지 올라가는 방법은 적어도 하나 있다.

베시는 홀드를 하나씩 밟으며 벽을 오른다. 두 홀드 사이의 직선 거리가 1000밀리미터 이하일 때만 한 홀드에서 다른 홀드로 옮길 수 있고, 위, 아래, 오른쪽, 왼쪽 또는 이를 섞은 방향으로 움직일 수 있다. 지면에서 $H - 1000$ 밀리미터 이상 높은 홀드에 닿으면 거기서 벽 위 발판으로 올라설 수 있다. 처음에는 $Y$ 좌표가 1000밀리미터 이하인 홀드 중 아무 곳에서나 시작한다.

벽의 높이와 홀드의 위치가 주어질 때, 베시가 꼭대기에 닿으려면 홀드를 최소 몇 개 밟아야 하는지 구하라.

• 첫째 줄에 $H$ 와 $F$ 가 공백으로 구분되어 주어진다.
• 둘째 줄부터 $F$ 개의 줄에 홀드 하나의 $X$ 좌표와 $Y$ 좌표가 공백으로 구분되어 주어진다. $X$ 는 벽 왼쪽 끝에서의 거리, $Y$ 는 지면에서의 높이이며 $0 \le X \le 30000$, $0 \le Y \le H$ 이다.

• 첫째 줄에 베시가 벽 꼭대기에 닿기 위해 밟아야 하는 홀드 개수의 최솟값을 출력한다. 이 개수에는 처음 밟는 홀드와 발판으로 올라설 때 딛는 마지막 홀드가 모두 들어간다.