Областная олимпиада по информатике 2015 года за 11 класс | Казахстанские олимпиады

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

Ограничение по времени Ограничение по памяти
1 секунда 64 мегабайта

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

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

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

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

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

Примеры

Вход

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

Выход

31