농부 창호의 친한 동생 진욱이는 강원도의 산간지대에 산다.

그는 최근에 소들에게 스키 타는 법을 가르쳤다.

하지만 그의 소들은 다소 소심해서 많은 사람 앞에서 스키타고 싶지 않기 때문에 그는 그의 농장에 새로 스키를 탈 수 있는 스키장을 짓기로 했다.

진욱이가 만들게 되는 스키장은 너비 W 길이 L의 구역이다.

(구역은 정사각형들로 구성되어 있으며 너비와 길이의 제한 조건은 다음과 같다.1≤W≤500, 1≤L≤500).

각 정사각형 구역은 해발 H(0≤H≤9,999)의 높이를 가진다.

소들은 수평이나 수직으로 인접한 두 구역으로 스키를 타고 이동할 수 있는데 대각선 방향으론 이동할 수 없으며

또한 높은데서 낮은 곳이나 높이가 같은 곳 사이는 이동할 수 있지만 다른 방법으로는 이동할 수 없다.

진욱이는 스키와 스키리프트를 적절히 이용해서 어떤 지점에서도 다른 어떤 지점으로 이동할 수 있도록 하고 싶다.

스키 리프트는 높이에 관계없이 임의의 두 지점 사이를 연결하도록 지을 수 있다(또 양방향이다).

진욱이는 스키 리프트가 비싸기 때문에 최소 개수만을 사용해서 위와 같은 조건을 만족시키려고 한다.

스키장 짓기 timer 1s memory 128MB

스키장 짓기 1s 128MB