Under construction

Still being built. Things may change

Maximum Distance

Interview

Time limit1sMemory limit128 MB

Summary
Given up to 50,000 points, compute the maximum L1 (Manhattan) distance between any two of them.
Level

Medium4 of 10

Topics
Math, Greedy, Array
Solved
No attempts yet

Problem

Given N points (1 <= N <= 50,000), find the maximum L1-metric distance between two of the given points.

For two points with coordinates (a, b) and (c, d), their L1-metric distance is |a-c| + |b-d|.

Input

The first line contains the number of points N.

Each of the next N lines contains the x-coordinate and y-coordinate of one point. Every coordinate is between -1,000,000 and 1,000,000, inclusive.

Output

Print the maximum L1-metric distance between the given points.

Examples1

  1. Example 1

    Input
    5
1 1
3 5
2 7
8 1
4 4
    Expected output
    12