==Include(page="template/taskheader" task_id="petrica")==
 
==Include(page="template/raw")==
 
Petrica
 
 
 
Petrica este presedintele unei tari cu N orase conectate prin strazi bidirectionale astfel incat exista un drum unic intre oricare doua dintre ele. Aceste orase sunt numerotate de la 1 la N astfel incat nu exista doua orase cu acelasi numar. Petrica vrea sa le imparta in patru districte blocand exact trei strazi. De asemenea vrea ca populatia oraselor sa fie distribuita cat mai uniform: diferenta dintre numarul de locuitori din distructul cu cea mai mare populatie si numarul de locuitori din districtul cu cea mai mica populatie sa fie cat mai mica. Aflati pentru presedintele Petrica aceasta diferenta.
 
 
 
Data de intrare: petrica.in
 
S pe prima linie numarul N reprezentand numarul de orase
 
S urmatoarea linie contine populatia fiecarui oras (N valori intregi)
 
S urmatoarele linii contin cate doi intregi A si B cu semnificatia: exista o strada intre orasele A si B
 
 
 
Data de iesire: petrica.out
 
S pe prima linie a fisierului se va afla un numar natural reprezentand diferenta minima pe care vrea sa o afle Petrica
 
h2. Restrictii si precizari
 
S 4 <= N <= 200
 
S Populatia fiecarui oras este un numar intreg din intervalul [1, 10000]
 
S Populatia unui district se calculeaza ca suma populatiei oraselor din districtul respectiv
 
S Doua orase sunt in acelasi district daca se poate ajunge de la unul la altul mergand pe strazi care nu au fost blocate
 
S Pentru 50% din teste N <= 70
 
h2. Exemplu
 
petrica.in petrica.out
4 1
 
2 1 1 1
 
1 2
 
1 3

==Include(page="template/taskheader" task_id="petrica")==
 
 
Petrica este presedintele unei tari cu $N$ orase conectate prin strazi bidirectionale astfel incat exista un drum unic intre oricare doua dintre ele. Aceste orase sunt numerotate de la $1$ la $N$ astfel incat nu exista doua orase cu acelasi numar. Petrica vrea sa le imparta in patru districte blocand exact trei strazi. De asemenea vrea ca populatia oraselor sa fie distribuita cat mai uniform: diferenta dintre numarul de locuitori din distructul cu cea mai mare populatie si numarul de locuitori din districtul cu cea mai mica populatie sa fie cat mai mica. Aflati pentru presedintele Petrica aceasta diferenta.
 
h2. Data de intrare
 
Prima linie a fisierului $petrica.in$ va contine numarul $N$ reprezentand numarul de orase. A doua linie contine populatia fiecarui oras ({$N$} valori intregi). Urmatoarele linii contin cate doi intregi $A$ si $B$ cu semnificatia: exista o strada intre orasele $A$ si $B$.
 
h2. Data de iesire
 
Pe prima linie a fisierului $petrica.out$ se va afla un numar natural reprezentand diferenta minima pe care vrea sa o afle Petrica.
 
h2. Restrictii si precizari
 
* $4 ≤ N ≤ 200$
* Populatia fiecarui oras este un numar intreg din intervalul $[1, 10000]$
* Populatia unui district se calculeaza ca suma populatiei oraselor din districtul respectiv
* Doua orase sunt in acelasi district daca se poate ajunge de la unul la altul mergand pe strazi care nu au fost blocate
* Pentru $50%$ din teste $N ≤ 70$
 
h2. Exemplu
 
table(example). |_. petrica.in |_. petrica.out |
| 4
2 1 1 1
1 2
1 3
1 4
| 1 |
 
==Include(page="template/taskfooter" task_id="petrica")==

1 4
==Include(page="template/taskfooter" task_id="petrica")==

40