시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 20 11 7 43.750%

## 문제

A group of Czech tourists is walking in a labyrinth of a strange self-similar shape. The ground plan of the labyrinth is a Sierpinski triangle – a fractal structure named after the Polish mathematician Wacław Sierpiński.

The labyrinth consists of a billion rows numbered from 0 to 109−1 from top to bottom, and a billion columns numbered from 0 to 109 − 1 from left to right. The fields in the labyrinth can be either free or blocked.

The field in row X and column Y is free if the result of the bitwise ‘and’ operation on the numbers X and Y is equal to zero, otherwise it is blocked. In other words, a field is blocked if, when X and Y are switched to binary, there is an integer k such that the kth digit from the right of the number X and the kth digit from the right of the number Y are equal to 1.

The first 32 rows and columns of the labyrinth. The blocked fields are colored in black.

The Czech tourists are tired from a long day of wandering and would like to meet up in a free field and exchange experiences. In each step, one tourist can jump to one of the adjacent free fields (up, down, left or right).

Write a programme that will, based on the current tourists’ locations, determine minimum total number of steps necessary in order for all the tourists to meet in the same field.

## 입력

The first line of input contains an integer N – the number of tourists. Each of the following N lines contains two integers Ri and Si – the row and column of the field where the i th tourist is located. (2 ≤ N ≤ 105, 0 ≤ RK, SK < 109)

All the tourists are located in free fields, and it is possible that there are multiple tourists in the same field.

## 출력

The first and only line of output must contain the required minimum number of steps.

Please note: We recommend that you use a 64-bit integer data type (int64 in Pascal, long long in C/C++).

## 예제 입력

2
2 1
4 3


## 예제 출력

6


## 예제 입력 2

6
2 5
3 4
8 7
9 6
10 5
11 4


## 예제 출력 2

50


## 힌트

Clarification of the first example: One of the fields where the brave Czech tourists could have met is (2, 0).

Clarification of the second example: One of the fields where the playful Czech tourists could have met is (8, 4).