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 to from top to bottom, and a billion columns numbered from to from left to right. The fields in the labyrinth can be either free or blocked.
The field in row and column is free if the result of the bitwise and
operation on the numbers and
is equal to zero, otherwise it is blocked. In other words, a field is blocked if, when and are switched
to binary, there is an integer such that the digit from the right of the number and the digit from
the right of the number are equal to .
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 the minimum total number of steps necessary in order for all the tourists to meet in the same field.
Input Specification
The first line of input contains an integer – the number of tourists. Each of the following lines contains two integers and – the row and column of the field where the tourist is located.
All the tourists are located in free fields, and it is possible that there are multiple tourists in the same field.
Output Specification
The first and only line of output must contain the required minimum number of steps.
Please note: We recommend that you use a -bit integer data type (int64
in Pascal, long long
in C/C++).
Constraints
Subtask | Score | Constraints |
---|---|---|
, | ||
, | ||
, | ||
, |
Sample Input 1
2
2 1
4 3
Sample Output 1
6
Explanation for Sample Output 1
One of the fields where the brave Czech tourists could have met is .
Sample Input 2
6
2 5
3 4
8 7
9 6
10 5
11 4
Sample Output 2
50
Explanation for Sample Output 2
One of the fields where the playful Czech tourists could have met is .
Comments