시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1090 297 200 26.316%

문제

프랑스에서 공부를 하고 돌아온 선아는 자신이 그렇게도 되고 싶어 했던 파티셰가 되었다. 케익 배달 전문업체 보나뻬띠에 취직한 선아는 친절하게도 자신이 만든 케익을 고객들에게 직접 배달을 하려 한다. N명의 고객에게 케익을 배달하는데 주문이 들어온 순서대로 배달하기를 원하며 고객이 케익을 받을 수 있을 만큼 충분히 가까이까지 배달한다.

N명의 고객의 위치는 순서대로 100,000×100,000 격자의 정수 좌표로 주어지고 처음 출발하게 되는 보나뻬띠의 위치도 정수 좌표로 주어진다. 선아는 격자 위에서 상하좌우로만 움직이며 고객에게 케익을 전달하기 위해서는 그 고객의 위치까지 가거나 고객의 상하좌우 인접 격자점에 가야 한다. 이 때 선아가 최단거리를 이동하여 입력된 순서대로 배달을 끝낼 수 있는 거리를 계산하는 프로그램을 작성하시오. 여기서 거리는 격자 상의 칸 수를 말한다.

위의 예에서 선아는 11칸을 움직여서 세 명의 고객에게 배달을 마칠 수 있다. 선아는 반드시 고객들에게 순서대로 배달을 하며 순서에 어긋난 사람에게 배달을 할 수 있는 위치에 있더라도 케익을 주지 않고 순서대로 배달을 한다. 고객의 위치는 중복이 될 수도 있다.

입력

첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다.
  (1 ≤ N, X, Y ≤ 100,000)

출력

첫째 줄에 최단 거리를 출력한다.

예제 입력

3
2 2
3 6
6 7
7 3

예제 출력

11

힌트