Problemas
품평회에서 가장 매력적인 것 중 한 가지는 벽 타기이다. 영희는 자신의 벽 타기를 잘 계획하고 싶고, 당신의 도움이 필요하다.
벽은 30,000mm 만큼 넓고 높이 H(1001≤H≤30,000mm)를 가진다. 또 F개의 (1≤F≤10,000) 발굽-지지대들을 각기 고유한 좌표 (X, Y)에 가지고 있다(mm 단위). 0, 0은 벽의 왼쪽 땅 부분을 말한다. 발굽-지지대는 각기 최소한 300mm씩은 떨어져 있다. 영희는 다음의 방법으로 벽을 탈 수 있다.
영희는 자신이 아는 테크닉들만을 이용해, 연속적으로 위치한 발굽-지지대들만을 사용해서 벽을 탄다. 그녀는 한 지지대에서 1m 보다 멀리 떨어지지 않은 다른 지지대로 이동할 수 있다. 물론, 영희는 위, 아래, 오른쪽, 왼쪽, 혹은 이 방향들의 적절한 조합을 통해 이동할 수 있다. 마찬가지로, 영희가 땅에서 최소한 H-1000mm 만큼 올라가야만, 그녀가 그곳에서 벽의 꼭대기로 올라갈 수 있다. 영희는 Y≤1000mm인 임의의 X위치에서 시작할 수 있다.
벽의 높이와 지지대들의 좌표가 주어졌을 때, 꼭대기에 가기 위해 최소로 사용해야 하는 지지대의 수를 결정하시오.
Entrada
1번째 줄: 공백으로 구분된 두 개의 정수 H와 F가 주어진다. 2번째 ~ F+1번째 줄: 각각의 줄은 공백으로 구분된 두 개의 정수 (각각 X와 Y)를 포함하는데, 지지대의 위치를 알려준다. X는 벽의 왼쪽으로부터의 거리, Y는 땅에서부터의 높이를 나타낸다.
Salida
1번째 줄: 영희가 벽의 꼭대기로 가기 위해 사용해야 하는 최소의 지지대 수를 출력한다.
Ejemplo
3000 5
600 800
1600 1800
100 1300
300 2100
1600 2300
3
Debes iniciar sesión para escribir código.