거름 순간이동 장치

농부 존이 가장 싫어하는 농장 일은 거름을 잔뜩 실어 나르는 일이다. 이 일을 줄이려고 존은 거름 순간이동 장치를 만들었다. 트랙터 뒤에 수레를 달고 두 지점 사이를 오갈 필요 없이, 거름을 한 지점에서 다른 지점으로 즉시 보낸다.

존의 농장은 곧게 뻗은 도로 하나를 따라 있어서, 농장의 모든 위치는 도로 위의 좌표 하나로 나타낼 수 있다. 즉 수직선 위의 점이다. 순간이동 장치는 두 수 $x$와 $y$로 정해진다. 위치 $x$로 가져온 거름은 즉시 위치 $y$로 옮겨진다.

존은 한쪽 끝점을 $x = 0$에 두기로 했다. 남은 끝점 $y$를 어디에 둘지 정해야 한다. 농장에는 거름 더미가 $N$개 있다($1 \le N \le 100{,}000$). $i$번째 더미는 위치 $a_i$에서 위치 $b_i$로 옮겨야 하고, 각 더미는 따로 옮긴다. $i$번째 더미를 실은 채 트랙터로 달린 거리를 $d_i$라고 하자. 트랙터로 곧장 끌고 가면 $d_i = |a_i - b_i|$이다. 순간이동 장치를 쓰면 $a_i$에서 $x$까지 간 다음 $y$에서 $b_i$까지 가므로 $d_i = |a_i| + |y - b_i|$이다. 존은 두 경로 중 짧은 쪽을 고른다. 모든 더미를 옮기는 동안 같은 $y$를 쓴다.

$d_i$의 합이 가장 작아지도록 $y$를 정했을 때, 그 합을 구하라.

첫째 줄에 $N$이 주어진다. 이어지는 $N$개의 줄 중 $i$번째 줄에 $a_i$와 $b_i$가 주어진다. 두 값 모두 $-10^8$ 이상 $10^8$ 이하의 정수이고, 서로 다르다는 보장은 없다.

$d_i$의 합의 최솟값을 정수 하나로 출력한다. 이 값은 32비트 정수 범위를 넘을 수 있으므로, 필요한 언어에서는 64비트 정수형을 쓴다.

첫 번째 예제에서 $y = 8$로 두면 $d_1 = 2$, $d_2 = 5$, $d_3 = 3$이 된다. $y$가 $7$ 이상 $10$ 이하이면 어떤 값이어도 합은 같다.