Traim intr-o lume ciudata, in care statiile de metrou sunt si mai ciudate. Iar pe cat de ciudat, pe atat de aglomerat. Fiind multa imbulzeala, avem nevoie de ajutorul vostru pentru a face ordine prin multime.
Un metrou are n usi. In momentul in care ajunge metroul in statie, stim ca la fiecare usa i, plasata in pozitia x[ i ] a axei Ox ( 1 <= i <= n ) sunt a[ i ] oameni care doresc sa intre in metrou si b[ i ] oameni care doresc sa iasa din metrou. Singura problema este ca, din cauza noilor reguli, printr-o usa se poate fie intra, fie iesi, una dintre aceste actiuni fiind intotdeauna interzisa. Niciunul dintre oamenii care fie vor sa intre in metrou, fie vor sa iasa nu stiu daca usa la care sunt amplasati este de deschidere sau de inchidere. Asa ca, daca in caz usa i din pozitia x[ i ] ( 1 <= i <= n ) este de intrare, cei b[ i ] oameni amplasati la aceasta usa vor fi nevoiti sa se mute la cea mai apropiata usa de iesire pentru a cobori la aceasta statie. Se mai stie ca efortul unui om de a se deplasa de la usa i la usa j este |x[ i ] - x[ j ]| ( 1 <= i, j <= n ).
Un metrou are $N$ usi. In momentul in care ajunge metroul in statie, stim ca la fiecare usa $i$, plasata in pozitia $x[i]$ a axei $Ox$ ({$1 ≤ i ≤ N$}) sunt $a[i]$ oameni care doresc sa intre in metrou si $b[i]$ oameni care doresc sa iasa din metrou. Singura problema este ca, din cauza noilor reguli, printr-o usa se poate fie intra, fie iesi, una dintre aceste actiuni fiind intotdeauna interzisa. Niciunul dintre oamenii care fie vor sa intre in metrou, fie vor sa iasa nu stiu daca usa la care sunt amplasati este de deschidere sau de inchidere. Asa ca, de exemplum daca usa $i$ din pozitia $x[i]$ ({$1 ≤ i ≤ N$}) este de intrare, cei $b[i]$ oameni amplasati la aceasta usa vor fi nevoiti sa se mute la cea mai apropiata usa de iesire pentru a cobori la aceasta statie. Se mai stie ca efortul unui om de a se deplasa de la usa $i$ la usa $j$ este $|x[i] - x[j]|$ ({$1 ≤ i, j ≤ N$}).
Avand la dispozitie numarul n de usi, pozitia acestora pe axa Ox si numarul de oameni care doresc sa intre si sa iasa din metrou la fiecare usa in parte, sa se gaseasca o intrebuintare a usilor de tipul 0 sau 1 ( 0 pentru usa de intrare, 1 pentru usa de iesire ), astfel incat efortul total depus de oameni pentru deplasare in urma intrarii si iesirii din metrou sa fie minim. Se cere aceasta configurare a usilor si in plus, efortul minim depus de oameni.
Avand la dispozitie numarul $N$ de usi, pozitia acestora pe axa $Ox$ si numarul de oameni care doresc sa intre si sa iasa din metrou la fiecare usa in parte, sa se determine efortul minim depus de oameni pentru deplasare in urma intrarii si iesirii din metrou.
h2. Date de intrare
In fisierul de intrare metrou.in se va afla pe prima linie numarul natural n, reprezentand numarul de usi ale metroului. Pe cea de-a doua linie se vor gasi valorile sirului x, unde x[ i ] reprezinta pozitia usii i. Pe liniile 3 si 4 se vor gasi valorile sirurilor a, respectiv b, reprezentand numarul de oameni care doresc sa intre, respectiv numarul de oameni care doresc sa iasa din metrou pe usile acestuia.
In fisierul de intrare $metrou.in$ se va afla pe prima linie numarul natural $N$, reprezentand numarul de usi ale metroului. Pe cea de-a doua linie se vor gasi valorile sirului $x$, unde $x[i]$ reprezinta pozitia usii $i$. Pe liniile $3$ si $4$ se vor gasi valorile sirurilor $a$, respectiv $b$, reprezentand numarul de oameni care doresc sa intre, respectiv numarul de oameni care doresc sa iasa din metrou pe usile acestuia.
h2. Date de ieşire
In fisierul de iesire metrou.out se va afla pe prima linie configurarea usilor de tipul 0101100101 ( 0 pentru usa de intrare, 1 pentru usa de iesire ), iar pe cea de-a doua linie efortul minim depus de oameni pentru a isi implini menirea =)).
In fisierul de iesire metrou.out se va afla pe prima si singura linie un singur numar natural reprezentand efortul minim depus de oameni pentru a-si indeplini scopul (intra/iesi din metrou).
h2. Restricţii
* $1 ≤ 2000 ≤ N$
* $2 ≤ N ≤ 2000$
* $0 ≤ x[i] ≤ 100.000$
* $1 ≤ a[i], b[i] ≤ 1000$
* $Elementele sirului x sunt in ordine crescatoare.$
* $Se garanteaza ca raspunsul intra in 32 de biti cu semn.$
h2. Exemplu
table(example). |_. metrou.in |_. metrou.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
1 3 4 5
1 2 3 5
2 3 3 1
| 9
|
h3. Explicaţie
...
Prima si a treia usa for fi de iesire, iar a doua si a patra usa de intrare.
Efortul depus de oamenii care vor sa intre este $1*2 + 2*0 + 3*1 + 5*0 = 5$
Efortul depus de oamenii care vor sa iasa este $2*0 + 3*1 + 3*0 + 1*1 = 4$
Efortul total este $4 + 5 = 9$
== include(page="template/taskfooter" task_id="metrou") ==
