== include(page="template/taskheader" task_id="inundatii") ==

Anul acesta este foarte posibil ca in orasul lui Zaharel sa aiba loc inundatii. Zaharel trebuie sa se gandeasca la un plan prin care sa protejeze cele $N$ cladiri din orasul sau de inundatii. Pentru a simplifica problema vom considera o cladire ca fiind un punct in spatiu.  In plus, cladirile din orasul lui Zaharel au niste proprietati interesante:

Anul acesta este foarte posibil ca in orasul lui Zaharel sa aiba loc inundatii. Zaharel trebuie sa se gandeasca la un plan prin care sa protejeze cele $N$ cladiri din orasul sau de inundatii. Pentru a simplifica problema vom considera o cladire ca fiind un punct in spatiu. In plus, cladirile din orasul lui Zaharel au niste proprietati interesante:

* sunt numerotate cu numere distincte intre $1$ si $N$

* coordonatele sunt numere intregi

* cladirea cu numarul $i$ *domina* cladirea cu numarul $i+1$ pentru orice $1 &le; i < N$; formal, asta inseamna ca $X{~i~} > X{~i+1~}$, $Y{~i~} > Y{~i+1~}$ si $Z{~i~} > Z{~i+1~}$, unde $(X{~i~}, Y{~i~}, Z{~i~})$ reprezinta pozitia cladirii cu numarul $i$
Dupa o lunga analiza, Zaharel a ajuns la concluzia ca cel mai sigur mod de a evita inundatiile este mutarea cladirilor astfel incat cladirea $i$ sa domine cladirea $i-1$ pentru orice $1 < i &le; N$. Desigur, mutarea unei cladiri nu este o treaba usoara, asa ca Zaharel vrea sa minimize suma distantelor cu care se muta fiecare cladire.

h2. Date de iesire

In fisierul de iesire $inundatii.out$ se va scrie un singur numar *real* reprezentand suma distantelor cu care se muta fiecare cladire, in cazul cel mai favorabil.

In fisierul de iesire $inundatii.out$ se va scrie un singur numar natural, reprezentand suma distantelor cu care se muta fiecare cladire, in cazul cel mai favorabil.

h2. Restrictii
* $1 ≤ N ≤ 50.000$
* $0 ≤ X{~i~}, Y{~i~}, Z{~i~} ≤ 10^8^$

* Nu exista nici o restrictie pentru coordonatele cladirilor dupa mutare (pot fi negative, reale, etc.)

* Coordonatele la care se muta casele trebuie sa fie numere intregi

* Se considera ca distanta dintre doua puncte $(x{~1~},y{~1~},z{~1~})$ si $(x{~2~},y{~2~},z{~2~})$ este $|x{~1~}-x{~2~}|+|y{~1~}-y{~2~}|+|z{~1~}-z{~2~}|$
h2. Exemplu

== include(page="template/taskfooter" task_id="inundatii") ==

2603