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

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.