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

Cerință

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

Date de intrare

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 $x_{AS} \ y_{AS} \ x_{AP} \ y_{AP}$, 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 \ y_1 \ y_2 \dots \ y_h$, unde $y_1 \ y_2 \dots \ y_h$ sunt ordonatele intersecţiilor.

Date de ieșire

Fişierul de iesire campanie.out va conţine un singur număr natural reprezentând timpul minim fără activitate electorală în campania pentru preşedinţie.

Restricții și precizări

• $N$ este număr natural proprietatea că $2 \leq N \leq 18$
• Distanţa parcursă între două oraşe sau două intersecţii de coordonate $(x_1, y_1)$ şi $(x_2, y_2)$ se defineşte ca fiind $(x_1 - x_2)^2 + (y_1 - y_2)^2$.
• Numărul de străzi dintr-un oraş $\leq 1 \ 000$.
• Numărul de intersecţii de pe o stradă $\leq 1 \ 000$.
• Distanţele dintre două străzi consecutive ale aceluiaşi oraş $\leq 1 \ 000$.
• Toate ordonatele intersecţiilor dintr-un oraş şi cea a aeroportului pentru plecări sunt $\leq 10 \ 000$.
• Coordonatele pe harta cu oraşe sunt numere întregi din intervalul $[-10 \ 000, 10 \ 000]$.

Exemplu

campanie.in

3
100 0 30 0
3 10 20
2 0 20
2 10 20
3 10 30 0
0 0 10 0
2 100
1 0
2 0 10
200 0 300 0
2 100
1 0
1 0

campanie.out

97500

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