== 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
În fişierul de ieşire $portal3.out$ ...
Fişierul de ieşire $portal3.out$ va contine $T$ linii. Pe linia $i$ se va afla raspunsul pentru testul $i$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10.000$
* $1 ≤ N, M ≤ 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
table(example). |_. portal3.in |_. portal3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|1
50 50
10 5 20 4 3
27 19 35 16 5
19 23 42 40 11|67
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="portal3") ==
