30622번 - Rush & Slash

문제

거대한 정원을 관리하는 것은 힘들다. 정원 관리 업무 중에서도 특히 힘든 일은 잡초를 제거하는 일인데, 정원을 돌아다니며 무엇이 잡초인지 일일이 확인해야 하기 때문이다.

다행히도 정원사 요우무는 잡초들의 위치를 이미 알고 있다. 정원에는 $N$개의 잡초가 자라 있으며, $i$번 잡초의 좌표는 $(x_i, y_i)$다. 모든 잡초는 서로 다른 곳에 자라 있다. $(1 \leq i \leq N)$

요우무는 정원 한가운데에 서 있으며, 정원 한가운데의 좌표는 $(0, 0)$이다. 정원 관리는 다음 과정으로 이루어지며, 요우무는 모든 잡초를 제거할 때까지 이를 반복한다.

1. 원하는 잡초의 위치로 이동한다. 이동하는 경로에 잡초가 있어도 상관없다.
2. 벤다. 요우무는 그 자리에서 잡초를 베며, 벤 잡초는 사라진다. 또한, 요우무의 검격은 매우 강력하기 때문에 연결된 잡초들도 동시에 벨 수 있다.
   • 상하좌우 혹은 대각선 방향으로 인접한 두 잡초는 연결되었다고 한다. 또한 잡초 $a$와 잡초 $b$가 연결되었고, 잡초 $b$와 잡초 $c$가 연결되었다면 잡초 $a$와 잡초 $c$도 연결되었다고 한다.
3. 정원의 한가운데로 이동한다. 만약 베야 할 잡초가 더 이상 없다면 요우무는 한가운데로 이동하지 않고 그대로 정원 관리를 마친다.

단, 요우무는 $x$축 또는 $y$축에 평행한 방향으로만 이동할 수 있다.

요우무는 모든 잡초를 제거하기 위해 이동해야 하는 거리의 합을 최소화하려고 한다. 요우무를 대신해 이를 구해주자!

입력

첫 번째 줄에 잡초의 개수 $N$이 주어진다. $(1 \leq N \leq 100,円 000)$

2ドル$번째 줄부터 $N + 1$번째 줄까지, $i + 1$번째 줄에 $i$번 잡초의 좌표를 나타내는 두 정수 $x_i, y_i$가 공백을 사이에 두고 주어진다. $(-10^9 \leq x_i, y_i \leq 10^9)$

주어지는 모든 좌표는 서로 다르다.

출력

첫 번째 줄에 요우무가 모든 잡초를 제거하기 위해 이동해야 하는 거리의 합의 최솟값을 출력한다.

제한

힌트