3212：Rescue Alice

Long long ago, there was a princess named Alice. She was taken by the evil Cent Dragon. Many warriors had tried to rescue her, but none of them ever came back. One day, a prince called Jack showed up. He told the King that he would go to rescue Alice in voluntary. The King responded in despair, “It’s no use fighting with Cent Dragon.” But that did not stop Jack. He set off immediately for the rescue.

Jack rode his way to the mountain where Cent Dragon lived. Unfortunately, he lost himself in the forest before the mountain and was unable to find Cent Dragon’s castle. After wandering for a while, Jack saw an old man on a stone smiling at him. He was surprised by the encounter and asked the old man for the way. “The forest is cursed in spells. An ordinal human being won’t be able to find a way out.” said the old man, “If you want to go to Cent Dragon’s castle, you must find the Tree of Moon for help.”

In spite of hardships, Jack succeeded in locating the Tree of Moon – a big blue tree with spirits. He told his story to it, and it answered, “In this forest there are some magical wells. They are the entries of the mountain. You can see all of them on a high tower nearby. You choice of entry will decide how soon you can enter the mountain. Precisely speaking, the time it takes can be measured by the sum of the distances between the well you choose and the other ones.”

In that ancient times, distance was measured in a manner similar to what we now call the Manhattan distance. Positions of the wells were described in a Cartesian plane. Instead of taking the sum of absolute differences in the abscissa and the ordinate, distances in Jack’s adventure were found by taking the maximum of them. Given the coordinates of the wells, can you tell how much time did Jack need at least to spend entering the mountain to rescue Alice in terms of distance?

The input contains a single test case. The first line of input contains a positive integer N (N ≤ 100,000), the number of wells. Then follow N lines, each contains two integers x_i and y_i (|x_i|, |y_i| ≤ 1,000,000), which are the Cartesian coordinate of the ith well.