一片长方形的沼泽里栖息着 10 种青蛙。物种 i 的青蛙可以沿着 X 轴或 Y 轴从一个小山丘跳到另一个小山丘。最初,所有类型的青蛙都坐在坐标为 (0, 0) 的小丘上。您将获得沼泽中所有其他小丘的坐标。求从 (0, 0) 到任意小丘的最大曼哈顿距离,其中一只青蛙可以通过在小丘之间跳跃而到达该小丘。
(x1, y1) 和 (x2, y2) 之间的曼哈顿距离为 |x1 - x2| + |y1 - y2|。
输入
输入的第一行包含一个整数 N (1 ≤ N ≤ 100) - 小丘的数量。以下 N 行包含小丘的坐标,格式为“X Y”(- 20 ≤ X,Y ≤ 20)。所有小丘都是不同的,并且没有一个位于 (0, 0)。
输出
输出一个整数 - 一只青蛙通过在山丘之间跳跃可到达的任何山丘的最大曼哈顿距离。
示例
输入 #1
3 0 1 0 -2 0 3
输出 #1
3
输入 #2
5 0 1 0 2 0 3 2 2 2 4
输出 #2
6
输入 #3
1 18 0
输出 #3
0
注意
在第一个示例中,物种 1、2 和 3 的青蛙可以分别跳到第一、第二和第三个小山丘。
在第二个示例中,2 种青蛙可以跳到第二个小山丘,然后跳到第四个小山丘,最后跳到第五个小山丘。
在第三个例子中,没有青蛙能够到达小丘。