은비는 관광 명소로 유명한 소울시에서 여행을 계획하고 있다.

소울시는 남북 방향으로 뻗은 W개의 도로와 동서 방향으로 뻗은 H개의 도로에 의해 격자 모양으로 이루어져 있다. 남북 방향의 W개의 도로는 서쪽에서부터 차례대로 1, 2, ..., W의 번호가 매겨져 있고, 동서 방향의 H개의 도로는 남쪽에서부터 차례대로 1, 2, ..., H의 번호가 매겨져 있다. 서쪽에서 a번째 남북 방향의 도로와 남쪽에서 b번째 동서 방향의 도로의 교차로는 (a, b)로 표시된다.

또, 아래 그림과 같이 각 교차로의 북동쪽-남서쪽 방향으로 도로가 뻗어져 있다. 따라서 교차로 (a, b)에서 1개의 도로를 통해 (a-1, b), (a+1, b), (a, b-1), (a, b+1), (a-1, b-1), (a+1, b+1)로 갈 수 있고, 이 여섯 가지 경우 모두 1의 시간이 걸린다.

은비는 N개의 관광 명소를 어떤 순서로 방문할지 모두 계획했다. i번째로 방문할 관광 명소는 교차로 (X_i, Y_i)에 있다. 은비가 N개의 관광 명소를 방문하는 데 걸리는 최소 시간을 구하는 프로그램을 작성하여라. 단, 은비는 (X₁, Y₁)에서 여행을 시작하며, 같은 길을 두 번 이상 통과할 수 있다.

#2733 upload 18 done 9 how_to_reg 9

여행 timer 1s memory 64MB

#2733

여행 1s 64MB