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

Poveste şi cerinţă...

Derpina se afla intr-o matrice cu $N+1$ linii si $M+1$ coloane in elementul $0, 0$. Ea vrea sa ajunga cat mai repede la prietenul ei Derp care se afla in matrice in elementul $N, M$. La fiecare pas Derpina se poate muta intr-o casuta invecinata. Ca sa ajunga mai rapede la prietenul ei, Derpina a apelat la firma de portale. Aceasta a construit $3$ perechi de portale in matrice, $P{~1~}$ cu $P{~2~}$, $P{~3~}$ cu $P{~4~}$ si $P{~5~}$ cu $P{~6~}$. Fiecare portal $P{~i~}$ se afla in matrice la pozitia $X{~i~}, Y{~i~}$. Pentru a folosi perechea de portale $i$, Derpina trebuia sa se afle in matrice intr-o casuta unde se afla un portal din perechea $i$ si sa activeze portalul. Ea va ajunge instant in celalalt portal, dar timpul pentru activarea unui portal din perechea $i$ este $C{~i~}$. Derpinei ii place sa isi petreaca timpul in bucatarie si vrea sa stea cat mai putin timp in afara ei. Derpina va cere ajutorul si pentru asta trebuie sa calculati timpul minim in care ea ajunge la Derp.

h2. Date de intrare

Fişierul de intrare $portal3.in$ ...

Fişierul de intrare $portal3.in$ va contine pe prima linie un numar natural $T$ reprezentand numarul de teste. Pentru fiecare test pe prima linie se afla $N$ si $M$, pe a doua linie $X{~1~}$, $Y{~1~}$, $X{~2~}$, $Y{~2~}$, $C{~1~}$, pe a treia linie $X{~3~}$, $Y{~3~}$, $X{~4~}$, $Y{~4~}$, $C{~2~}$ si pe a patra linie $X{~5~}$, $Y{~5~}$, $X{~6~}$, $Y{~6~}$, $C{~3~}$.

h2. Date de ieşire

* $1 ≤ T ≤ 10.000$
* $1 ≤ N, M ≤ 1.000.000.000$

* $0 ≤ X1{~i~}, X2{~i~} ≤ N$
* $0 ≤ Y1{~i~}, Y2{~i~} ≤ M$
* $0 ≤ C{~i~} ≤ 1.000.000.000$

* $0 ≤ X{~1~}, X{~2~}, X{~3~}, X{~4~}, X{~5~}, X{~6~} ≤ N$
* $0 ≤ Y{~1~}, Y{~2~}, Y{~3~}, Y{~4~}, Y{~5~}, Y{~6~} ≤ M$
* $0 ≤ C{~1~}, C{~2~}, C{~3~} ≤ 1.000.000.000$

h2. Exemplu

19 23 42 40 11|67
|

h3. Explicaţie
 
...

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

6372