시에르핀스키 미로에서 모이기

체코에서 온 관광객 무리가 스스로를 닮은 이상한 모양의 미로를 걷고 있다. 미로의 평면도는 폴란드 수학자 바츠와프 시에르핀스키의 이름을 딴 프랙털인 시에르핀스키 삼각형이다.

미로는 위에서 아래로 $0$번부터 $10^9 - 1$번까지 번호가 붙은 10억 개의 행과, 왼쪽에서 오른쪽으로 $0$번부터 $10^9 - 1$번까지 번호가 붙은 10억 개의 열로 이루어진다. 각 칸은 빈 칸이거나 막힌 칸이다.

$X$행 $Y$열의 칸은 $X$와 $Y$의 비트 AND 연산 결과가 $0$이면 빈 칸이고, 그렇지 않으면 막힌 칸이다. 다시 말해 $X$와 $Y$를 이진수로 적었을 때 오른쪽에서 $k$번째 자리가 둘 다 $1$인 $k$가 존재하면 그 칸은 막혀 있다.

관광객들은 하루 종일 헤매고 다녀서 지쳤고, 빈 칸 하나에 모여 각자의 경험을 나누려고 한다. 한 번의 이동에서 관광객 한 명은 위, 아래, 왼쪽, 오른쪽으로 인접한 빈 칸 하나로 뛸 수 있다.

관광객들의 현재 위치가 주어지면 모두가 같은 칸에 모이는 데 필요한 전체 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 관광객의 수 $N$이 주어진다. ($1 \le N \le 100000$)

다음 $N$개 줄에는 $i$번째 관광객이 서 있는 칸의 행 번호 $R_i$와 열 번호 $S_i$가 공백을 사이에 두고 주어진다. ($0 \le R_i, S_i \le 10^9 - 1$)

모든 관광객은 빈 칸에 서 있다. 즉 $R_i$와 $S_i$의 비트 AND 연산 결과는 $0$이다. 한 칸에 관광객이 여러 명 서 있을 수도 있다.

첫째 줄에 필요한 이동 횟수의 최솟값을 출력한다.

답이 32비트 정수의 범위를 넘을 수 있으므로 64비트 정수 자료형(C나 C++의 long long, 파스칼의 int64)을 쓰는 편이 좋다.

첫 번째 예제에서 관광객들이 모일 수 있는 칸 중 하나는 (2, 0)이다.

두 번째 예제에서 관광객들이 모일 수 있는 칸 중 하나는 (8, 4)이다.