== 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.

Poveste şi cerinţă...

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 ≤ X1{~i~}, X2{~i~} ≤ N$
* $0 ≤ Y1{~i~}, Y2{~i~} ≤ M$
* $0 ≤ C{~i~} ≤ 1.000.000.000$

h2. Exemplu