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

Un candidat la preşedinţia unui mare stat al lumii a intrat în campania electorală. Pentru a obţine cât mai multe voturi, echipa de campanie doreşte ca timpul fără activitate electorală să fie cât mai mic. Acest timp se măsoară prin distanţa pe care o parcurge mergând cu avionul între oraşe şi prin deplasarea în interiorul oraşelor pe drumuri fără alegători. Toate oraşele alese pentru campanie au aceeaşi structură arhitecturală, adică fiecare conţine câte două aeroporturi notate cu AS şi AP, AS numai pentru sosiri, iar AP numai pentru plecări. Străzile fiecărui oraş sunt paralele, două străzi paralele consecutive sunt legate prin drumuri fără alegători, punctele unde se face legătura cu acestea sunt intersecţii. Orice două intersecţii de pe străzi paralele consecutive sunt legate printr-un drum, în linie dreaptă. Toate străzile au case şi implicit şi alegători. AS este pe prima stradă, în punctul cel mai din stânga jos, iar AP pe ultima stradă, cea mai din dreapta a oraşului.

Un candidat la preşedinţia unui mare stat al lumii a intrat în campania electorală. Pentru a obţine cât mai multe voturi, echipa de campanie doreşte ca timpul fără activitate electorală să fie cât mai mic. Acest timp se măsoară prin distanţa pe care o parcurge mergând cu avionul între oraşe şi prin deplasarea în interiorul oraşelor pe drumuri fără alegători. Toate oraşele alese pentru campanie au aceeaşi structură arhitecturală, adică fiecare conţine câte două aeroporturi notate cu $AS$ şi $AP$, $AS$ numai pentru sosiri, iar $AP$ numai pentru plecări. Străzile fiecărui oraş sunt paralele, două străzi paralele consecutive sunt legate prin drumuri fără alegători, punctele unde se face legătura cu acestea sunt intersecţii. Orice două intersecţii de pe străzi paralele consecutive sunt legate printr-un drum, în linie dreaptă. Toate străzile au case şi implicit şi alegători. $AS$ este pe prima stradă, în punctul cel mai din stânga jos, iar $AP$ pe ultima stradă, cea mai din dreapta a oraşului.
 

Un exemplu de structură arhitecturală pentru un oraş este prezentat mai jos.

Echipa de campanie are la dispoziţie o hartă cu coordonatele aeroporturilor a N oraşe şi N hărţi, câte una pentru fiecare oraş, cu coordonatele intersecţiilor de pe fiecare stradă.
	Sistemul de coordonate pentru fiecare oraş are originea în aeroportul pentru sosiri AS, străzile fiind paralele cu axa ordonatelor, iar aeroportul pentru plecări AP se află pe ultima stradă (cea mai din dreapta). Axa ordonatelor este prima stradă (cea mai din stânga stradă).
	Plecarea în campanie se face dintr-un aeroport de sosiri a unui oraş, iar sfârşitul pe acelaşi aeroport. Obligatoriu candidatul trece prin toate aeroporturile.

!problema/campanie?campanie.bmp!
 
Echipa de campanie are la dispoziţie o hartă cu coordonatele aeroporturilor a $N$ oraşe şi $N$ hărţi, câte una pentru fiecare oraş, cu coordonatele intersecţiilor de pe fiecare stradă.
Sistemul de coordonate pentru fiecare oraş are originea în aeroportul pentru sosiri $AS$, străzile fiind paralele cu axa ordonatelor, iar aeroportul pentru plecări $AP$ se află pe ultima stradă (cea mai din dreapta). Axa ordonatelor este prima stradă (cea mai din stânga stradă).
Plecarea în campanie se face dintr-un aeroport de sosiri a unui oraş, iar sfârşitul pe acelaşi aeroport. Obligatoriu candidatul trece prin toate aeroporturile.

Determinaţi timpul minim fără activitate electorală în campania pentru preşedinţie.

Fişierul de intrare $campanie.in$ va avea următoarea structură:

* pe prima linie se află N, numărul de oraşe
* pe următoarele linii se află datele pentru structura arhitecturală a fiecărui oraş: o linie cu coordonatele aeroporturilor xAS yAS xAP yAP, separate prin câte un spaţiu, o linie cu numărul k de străzi urmat de k-1 numere cu distanţele dintre două străzi consecutive, separate prin câte un spaţiu de la stânga la dreapta, apoi k linii cu poziţiile intersecţiilor de pe fiecare stradă în formatul: h y1 y2 …yh, unde y1, y2, …, yh sunt ordonatele intersecţiilor.

* pe prima linie se află $N$, numărul de oraşe
* pe următoarele linii se află datele pentru structura arhitecturală a fiecărui oraş: o linie cu coordonatele aeroporturilor $xAS$ $yAS$ $xAP$ $yAP$, separate prin câte un spaţiu, o linie cu numărul $k$ de străzi urmat de $k-1$ numere cu distanţele dintre două străzi consecutive, separate prin câte un spaţiu de la stânga la dreapta, apoi $k$ linii cu poziţiile intersecţiilor de pe fiecare stradă în formatul: $h y1 y2 …yh$, unde $y1, y2, …, yh$ sunt ordonatele intersecţiilor.

h2. Date de ieşire

h2. Restricţii

* N este număr natural proprietatea că  2 ≤ N ≤ 18
* Distanţa parcursă între două oraşe sau două intersecţii de coordonate (x1,y1) şi (x2,y2) se defineşte ca fiind (x1-x2)2 + (y1-y2)2.
* Numărul de străzi dintr-un oraş ≤ 1000.
* Numărul de intersecţii de pe o stradă  ≤ 1000.
* Distanţele dintre două străzi consecutive ale aceluiaşi oraş  ≤ 1000.
* Toate ordonatele intersecţiilor dintr-un oraş şi cea a aeroportului pentru plecări sunt ≤ 10000.
* Coordonatele pe harta cu oraşe sunt numere întregi din intervalul [-10000, 10000].
* $... ≤ ... ≤ ...$

* $N$ este număr natural proprietatea că $2$ $≤$ $N ≤$ $18$
* Distanţa parcursă între două oraşe sau două intersecţii de coordonate $(x1,y1)$ şi $(x2,y2)$ se defineşte ca fiind (x1 - x2)^2^ + (y1 - y2)^2^.
* Numărul de străzi dintr-un oraş $≤ 1000$.
* Numărul de intersecţii de pe o stradă $≤ 1000$.
* Distanţele dintre două străzi consecutive ale aceluiaşi oraş $≤ 1000$.
* Toate ordonatele intersecţiilor dintr-un oraş şi cea a aeroportului pentru plecări sunt $≤ 10000$.
* Coordonatele pe harta cu oraşe sunt numere întregi din intervalul $[-10000, 10000]$.

h2. Exemplu

h3. Explicaţie

...

Ordinea oraşelor în care va ajunge candidatul este $1, 2, 3$. În oraşul $1$ timpul fără activitate electorală va fi $500$, în oraşul $2$ va fi $10000$, iar în oraşul $3$ va fi $10000$.

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