품평회에서 가장 매력적인 것 중 한 가지는 벽 타기이다. 영희는 자신의 벽 타기를 잘 계획하고 싶고, 당신의 도움이 필요하다.

벽은 30,000mm 만큼 넓고 높이 H(1001≤H≤30,000mm)를 가진다. 또 F개의 (1≤F≤10,000) 발굽-지지대들을 각기 고유한 좌표 (X, Y)에 가지고 있다(mm 단위). 0, 0은 벽의 왼쪽 땅 부분을 말한다. 발굽-지지대는 각기 최소한 300mm씩은 떨어져 있다. 영희는 다음의 방법으로 벽을 탈 수 있다.

영희는 자신이 아는 테크닉들만을 이용해, 연속적으로 위치한 발굽-지지대들만을 사용해서 벽을 탄다. 그녀는 한 지지대에서 1m 보다 멀리 떨어지지 않은 다른 지지대로 이동할 수 있다. 물론, 영희는 위, 아래, 오른쪽, 왼쪽, 혹은 이 방향들의 적절한 조합을 통해 이동할 수 있다. 마찬가지로, 영희가 땅에서 최소한 H-1000mm 만큼 올라가야만, 그녀가 그곳에서 벽의 꼭대기로 올라갈 수 있다. 영희는 Y≤1000mm인 임의의 X위치에서 시작할 수 있다.

벽의 높이와 지지대들의 좌표가 주어졌을 때, 꼭대기에 가기 위해 최소로 사용해야 하는 지지대의 수를 결정하시오.

#1182 upload 15 done 3 how_to_reg 3

벽타기 timer 1s memory 64MB

#1182

벽타기 1s 64MB