传统题 1000ms 256MiB

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

福建师范大学第十九届程序设计竞赛重现赛

未参加
状态
已结束
规则
IOI
题目
13
开始于
2022-5-21 6:30
结束于
2023-4-19 14:30
持续时间
8000 小时
主持人
参赛人数
32