Областная олимпиада по информатике. 9 класс. 2014-2015 учебный год.

Задача B. Тима и точки

Ограничение по времени:

1 секунда

Ограничение по памяти:

64 мегабайта

Один очень сильный мальчик по имени Тима поймал Вас на переулке Манхэттена. Единственный шанс уйти без повреждений — решить следующую задачу! Даны $N$ точек в пространстве. Требуется найти две самые удалённые точки. Расстояние между точками $(x_1; y_1; z_1)$ и $(x_2; y_2; z_2)$ равно $|x_1-x_2|+|y_1-y_2| + |z_1-z_2|$. Решите задачу и спасите себя!

Формат входного файла

В первой строке задано целое число $N$ $(2 \le N \le 10^5)$ — количество точек. В следующих $N$ строках заданы сами точки — по три целых числа $x_i;$ $y_i;$ $z_i$ на каждой строке. Все координаты точек находятся в интервале $[-10^6 \ldots 10^6]$.

Формат выходного файла

Выведите ответ к задаче.

Примеры:

Вход

4
0 9 -8
-2 5 3
6 -6 2
7 1 6

Ответ

31

Замечание

Ответ 31, потому что расстояние между 1-ой и 3-ей точками равно $|0-6| + |9-(-6)| + |-8-2| = 6 + 15 + 10 = 31;$
$2 \le N \le 10^4$ — для $30\%$ тестов