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

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, P1 cu P2, P3 cu P4 si P5 cu P6. Fiecare portal Pi se afla in matrice la pozitia Xi, Yi. 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 Ci. Derpina va cere ajutorul si pentru asta trebuie sa calculati timpul minim in care ea ajunge la Derp.

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~}$. Derpina va cere ajutorul si pentru asta trebuie sa calculati timpul minim in care ea ajunge la Derp.

h2. Date de intrare

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

* $0 ≤ X1, X2, X3, X4, X5, X6 ≤ N$
* $0 ≤ Y1, Y2, Y3, Y4, Y5, Y6 ≤ M$
* $0 ≤ C1, C2, C3 ≤ 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") ==