Informatica Online Judge

  텔레포테이션(Silver) [2191 / 088F]

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


The Champion of this Problem (C++) : gs15120 - 0ms / 1496byte
My Best Submission (C++) : N/A

[USACO 2018(Dhruv Rohatgi & Brian Dean)]

Background

농장 일들 중에서 농부 존이 가장 싫어하는 일은, 아주 많은 젖소 똥들을 이리 저리 옮기는 일이다.

이런 일을 효율적으로 하기 위해, 멋진 발명품을 만들었다.: 똥 텔레포터!

똥 텔레포터를 이용하면, 수레가 달린 트랙터를 끌고 두 지점을 직접 왔다갔다하지 않아도 된다.

농부 존의 농장은 하나의 직선 도로를 따라 만들어져 있기 때문에, 농장의 어떤 위치는 직선 도로의 위치를 표시하는 수로 쉽게 표현할 수 있다.

똥 텔레포터를 사용하면 x위치에 있는 똥을 y위치로 순간적으로 이동시킬 수 있다.

농부 존은 x위치가 0에 있는 텔레포터를 하나 만들었는데, 가장 좋은 y위치를 알아내야 한다.


농장에는 N개의 똥 더미들이 있다. 각각의 i번째 똥 더미는 $a_i$ 위치에서 $b_i$ 위치로 옮겨져야 한다. i번째 똥 더미를 옮기는데 필요한 거리를 $d_i$라고 하면, i번째 똥 더미를 트랙터를 이용해 직접 옮기기 위해서는 $d_i$=|$a_i$−$b_i$| 만큼 이동시켜야 하지만, 텔레포터를 사용하면 더 적은 거리 만으로도 옮길 수도 있다.
(즉, $a_i$ 위치에서 x위치로 옮긴 후, y로 텔레포트 시켜 다시 $b_i$ 위치로 옮길 수도 있다.)

똥 덩어리들을 트랙터를 이용해 이동 시키는데 필요한 거리의 최소합을 찾아내보자. 모든 똥 더미들은 모두 같은 y위치를 사용한다.

Input

첫 번째 줄에는 똥 덩어리의 개수(N)가 입력된다.
그 다음 N개의 줄에는 i번째 똥 덩어리를 옮겨야할 $a_i$와 $b_i$가 공백을 두고 입력된다. 같은 값들이 있을 수 있다.

[입력값의 정의역]

$1≤N≤100,000$
$-10^8≤a_i, b_i≤10^8$

Output

트랙터를 이용해 이동 시키는데 필요한 거리의 최소합을 출력한다. 최소합이 정수인지 실수인지 궁금하게 생각할 수도 있을 것이지만...

IO Example

입력
3
-5 -7
-3 10
-2 7

출력
10

* 설명 :
y위치가 8이면 d1=2, d2=5, d3=3 로 가능하다. [7, 10] 범위에 있는 어떤 값이더라도 최소합이 된다.

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