Khoảng cách Manhattan lớn nhất

View as PDF

Submit solution

Points: 300 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Cho \(n \leq 3*10^5\) điểm trên mặt phẳng tọa độ Oxy. Bạn cần tính khoảng cách lớn nhất giữa 2 điểm bất kì.

Biết công thức tính khoảng cách Manhattan giữa 2 điểm \(A\) và \(B\) là \(|x_{A} - x_{B}| + |y_{A} - y_{B}|\).


Input

Dòng đầu tiên chứa một số nguyên \(n\).

Trong \(n\) dòng tiếp theo, mỗi dòng chứa 2 số \(x_i, y_i\) là tọa độ của điểm thứ \(i\).

Mọi điểm được cho đều có tọa độ nguyên và \(|x|,|y| \leq 10^9\).

Output

Một số nguyên duy nhất là kết quả của bài toán.


Ví dụ

Input

3
1 -2
3 7
-6 4

Output

13

Be the first to comment

Comments

There are no comments at the moment.