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

Poveste şi cerinţă...

Dorel are N găleţi numerotate de la 1 la N, fiecare găleata are o capacitate C în litri. Dorel are un furtun legat la o sursă infinită de apă şi doreşte să umple toate găleţile. Dorel însă, vrea să toarne acceaşi cantitate de apă în toate găleţile şi işi doreşte să umple toate găleţile turnând aceeaşi cantitate minimă în toate.
 
Pentru a face acest lucru, el a stabilit o ordine de exces, ordinea de exces înseamna că dacă o găleata s-a umplut şi înca mai este apă de turnat în ea, restul de apă va fi turnată în găleata următoare specificată în ordine. De exemplu, dacă ordinea este 1 -> 3 -> 2 -> 4, asta înseamnă că dacă găleata 1 se umple, restul se toarnă în găleata 3, dacă şi găleata 3 se umple, restul se toarna în găleata 2, dacă şi găleata 2 se umple, restul se toarna în găleata 4, excesul din găleata 4 este folosit pentru a uda florile, adică nu ne intereseaza.
 
În afară de ordinea de exces, Dorel va turna apă în găleţi în ordinea 1, 2, ... N
 
h2. Cerinţă
 
Stiind N, numărul de găleţi, capacitatea fiecarei găleţi şi ordinea de exces a găleţilor, aflaţi cantitatea minima de apă, în litri, necesară pentru a fi umplute toate găleţile. Determinaţi o ordine de vărsare mai buna astfel încât să minimalizaţi cantitatea minima de apă necesară pentru a umple toate găleţile şi afisaţi noua cantitate. Se garanteaza ca nu vor exista cicluri în ordinea de exces.

h2. Date de intrare

Fişierul de intrare $galeti.in$ ...

Prima linie a fişierului $galeti.in& va conţine numărul N cu semnificaţia din enunţ.
A 2-a linie conţine N numere ce reprezinta ordinea de exces.
A 3-a linie conţine N numere, al i-lea număr reprezinta capacitatea pentru găleata cu numărul i.

h2. Date de ieşire

În fişierul de ieşire $galeti.out$ ...
 

În fişierul $galeti.out$ afişaţi pe prima linie cantitatea necesară pentru a umple toate găleţile.
Pe a 2-a linie afişaţi noua ordine de exces, dacă există mai multe, afişaţi pe oricare dintre ele.
Pe a 3-a linie afişaţi noua cantitate minimă necesară pentru a umple toate găleţile.

h2. Restricţii

* $... ≤ ... ≤ ...$

* 1 ≤ N ≤ 10 ^5^
* 1 ≤ C ≤ 10 ^9^
* pentru 30% din punctaj: 1 ≤ N ≤ 600, 1 ≤ C ≤ 10000
* pentru 50% din punctaj 1 ≤ N ≤ 1000

h2. Exemplu
table(example). |_. galeti.in |_. galeti.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
1 2 3 4
4 2 4 2
| 4
2 3 4 1
3

|
h3. Explicaţie

...

Cu ordinea iniţiala de exces, valoarea minimă cerută este 4. Cu noua ordine de exces, excesul de 1 litru din găleata 2 se va turna în găleata 3 şi se va umble, excesul de 1 litru din găleata 4 se va turna în găleata 1 şi se va umple, raspuns final 3. O altă nouă ordine de exces validă putea fi: 2 4 1 3

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

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