문제
그리스 신들이 사는 현대식 도시에는 길거리의 도로들이 X, Y 축에 평행하며 정수 좌표로 된 격자 형태로 배열되어 있다.
임의의 정수 Z에 대해, y=Z로 표현되는 수평 도로가 있고, x=Z로 표현되는 수직 도로가 있다.
그래서 정수로 구성된 좌표는 수평· 수직 도로가 만나는 교차로가 된다.
날씨가 더우면 신들은 바로 이 교차로들 중 어디엔가 있는 카페테리아에 따로 따로 흩어져 쉰다.
신들의 심부름꾼인 헤르메스는 이날도 길거리의 도로만 이용하여 이동한 뒤,
여러 카페테리아에 흩어져 있는 신들에게 메시지를 부지런히 전달한다.
한 메시지는 한 신만을 대상으로 하고 있으나,
전달 과정에서 메시지가 다른 신이 있는 지점을 통과하더라도 상관은 없다.
헤르메스는 초기에 원점 (0, 0)에 있다.
전달 순서라는 개념이 존재하기 때문에 헤르메스는 자신에게 가까운 곳부터가 아니라
먼저 소식을 전해야 하는 신에게 먼저 메시지를 전달해야 한다.
단, 메시지는 직진하는 광자를 발사하는 방식으로 전하기 때문에,
헤르메스는 목적지인 신이 있는 곳과 x 위치가 같거나 y 위치가 같은 지점까지만 가면 된다.
전해야 하는 메시지를 모두 전하면 헤르메스의 임무는 끝난다.
가야 하는 카페테리아들의 위치를 입력으로 받아,
헤르메스가 각 지점들을 순서대로 방문하며 메시지를 전달하는 데 필요한 최소의 이동량을 계산하는 프로그램을 작성하라.
입력
첫째 줄에는 전해야 하는 메시지의 총 개수 N이 있다. 그리고 다음 N줄에는 각 메시지를 전하기 위해 방문해야 하는 카페테리아가 교차로의 어느 위치에 있는지, 그 좌표가 한 줄에 하나씩, X, Y 축 순으로 들어온다.
<제약조건> 모든 테스트 케이스에 대해서 다음과 같은 제약 조건이 주어진다. 1 ≤ N ≤ 20,000, -1000 ≤ 카페테리아의 X, Y좌표 ≤ 1000
또한, 전체 테스트 케이스 중 절반은 1≤ N ≤ 80이다.
출력
최소의 이동 거리를 나타내는 숫자 하나를 한 줄에다 출력한다.
예제
5
8 3
7 -7
8 1
-2 1
6 -5
11
로그인해야 코드를 작성할 수 있어요.