B.A. va da N
puncte in spatiu, cu coordonate numere intregi. Va cere distanta Manhattan dintre
cele mai departate 2 puncte
(tot folosind distanta Manhattan).
Reamintim ca distanta Manhattan dintre 2 puncte in spatiu cu coordonatele (X1, Y1, Z1) si respectiv (X2, Y2, Z2) este |X1 - X2| + |Y1 - Y2| + |Z1 - Z2|.
Cerinta
Ajutati-l pe Balaurul Arhirel sa se califice la finala .campion, rezolvandu-i aceasta problema, adica afland distanta Manhattan dintre cele mai departate 2 puncte.
Date de intrare
Pe prima linie a fisierului
distanta.in se afla N, reprezentand numarul de puncte. Pe urmatoarele N linii sunt cate 3 numere intregi separate printr-un spatiu, reprezentand in ordine, coordonatele X, Y si respectiv Z ale celor N puncte.
Date de iesire
Fisierul distanta.out
va contine o linie cu un singur numar intreg, si anume distanta cea mai mare
intre 2 puncte dintre
cele N.
Restrictii si precizari
1
< N < 100 001
-1000001
< X, Y, Z < 1000001, pentru toate cele N puncte
Exemplu
distanta.in
distanta.out
Explicatii
8
0 0 0
0 0 1
0 1 0
1 0 0
1 1 0
1 0 1
0 1 1
1 1 1
3
Distanta maxima este 3. De exemplu punctele (1,1,1) si (0,0,0).
Exista mai multe perechi de puncte cu aceeasi distanta maxima, insa distanta este una singura.