#P2022E. Cats or dogs?

    ID: 116 Type: Default 1000ms 256MiB Tried: 23 Accepted: 3 Difficulty: 9 Uploaded By: Tags>福建师范大学第19届程序设计竞赛

Cats or dogs?

Cats or dogs?

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

Frank is doing a research on how animals make humans closer. To describe the distance of two people AA and BB about an animal, he creates a formula: disA,B=xaxbdis_{A,B} = |x_a - x_b| if AA has a favorability xax_a for this animal and BB has a favorability xbx_b for the same kind animal. And then he starts from the most common animals: dogs and cats.

After a long and difficult statistical investigation, he surveyed nn people about their favorability xix_i for cats and their favorability yiy_i for dogs. He quickly finds that it is easy to calculate the maximum distance about cats or dogs among these people. For example, if he needs to find the maximum distance about cat, he just need to find the maximum xmaxx_{max} and the minimum xminx_{min}, then the maximum distance among these people is xmaxxmin|x_{max} - x_{min}|.

For further research, he wants to find the maximum distance about both cats and dogs, so he improvs the formula: disA,B=min(xaxb,yayb)dis_{A,B} = min(|x_a - x_b|,|y_a-y_b|) if AA has a favorability xax_a for cats and yay_a for dogs and BB has a favorability xbx_b for cats and yby_b for dogs.

Now, Frank is going to find the maximum distance among these nn people. It seems very easy too, so Frank gives this problem to you.

Input

The first line contains one integer n(2n105)n(2\leq n \leq 10^5).

In the following nn lines, each line contains two integers xi,yi(0xi,yi109)x_i,y_i(0\leq x_i,y_i \leq 10^9) denoting the favorability xix_i for cats and yiy_i for dogs.

Output

Print a single integer, denoting the answer to the question.

3
0 3
3 1
4 10
4