Informatica Online Judge

  evelynn [1929 / 0789]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 3   Total Tried : 5


The Champion of this Problem (C++) : gs16106 - 10ms / 1548byte
My Best Submission (C++) : N/A

[koistudy.net (34th 조승한)]
Writer ID : [gs16106]

Background

협곡의 지배자 승한이는 이블린 장인이다. 하지만 이블린에게 남다른 애착이 있어서 남이 이블린을 플레이 하면 불같이 화를 낸다.

피시방 아르바이트를 하는 승한이는 오늘따라 이블린을 플레이 하는 사람이 많아서 화가 많이 나있는 상태이다. 피시방은 좌표평면으로 일반화할 수 있고 각 격자점에 컴퓨터가 존재한다고 하자. 이제 승한이는 아르바이트생의 권위를 이용하여 이블린을 플레이 하는 사람들의 컴퓨터를 모조리 꺼버릴 것이다.

컴퓨터는 리모콘을 이용해서 끌 수 있고 이 리모콘은 같은 x좌표이거나 같은 y좌표에 있는 컴퓨터만을 끌 수 있다. 그래서 직접 이동하여야 하는데 이 이동거리를 최소화하고 싶다. 단, 끄는 컴퓨터의 순서는 정해져 있다.

승한이가 처음 시작하는 위치는 (0, 0)이고, 위, 아래, 양옆으로 이동할 수 있다. n개의 이블린을 플레이하고 있는 컴퓨터 위치가 순서대로 주어지면 승한이의 최소 이동거리를 출력하여라.

Input

첫 번째 줄에 컴퓨터의 개수를 의미하는 정수 n ( 1<=n<=5,000 )이 주어진다.

두 번째 줄부터 n+1번째 줄까지 각 컴퓨터의 x, y ( -10^9<=x, y<=10^9 )좌표가 순서대로 주어진다.

Output

첫 번째 줄에 최소 이동거리를 출력하여라.

IO Example

입력
3
2 1
3 -2
-3 -1

출력
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]