purification

După ce a cucerit Tarsonis, Tassadar a trecut la purificarea planetei Zerus. Această planetă este infestată şi are $N$ cuiburi zerg. Cuiburile sunt numerotate de la $0$ la $N - 1$ şi, în fiecare oră, cuibul $i$ produce $W_i$ zerglingi. Iniţial, pe planetă nu exista niciun zergling.

Un cuib este fie autonom, fie susţinut vital de un alt cuib. Dacă un cuib autonom este distrus, atunci producţia de zerglingi din acest cuib încetează şi toate cuiburile susţinute vital de acesta devin autonome. Dacă un cuib susţinut vital de un alt cuib este distrus, acesta se regenerează instantaneu, iar producţia de zerglingi rămâne neîntreruptă.

Tassadar poate distruge un cuib instantaneu folosind laserul de purificare de pe nava "Spear of Adun". Înainte să tragă, laserul trebuie să se încarce timp de o oră şi se descarcă de fiecare dată când trage. Iniţial, laserul este descărcat.

Tassadar vrea să distrugă permanent toate cuiburile, astfel încat la final să existe un număr minim de zerglingi.

Ajutaţi-l pe Tassadar să purifice planeta!

Date de intrare

Fişierul de intrare purification.in conţine pe prima linie numărul $N$ de cuiburi. Pe următoarea linie se vor afla $N$ numere $W_i$, semnificând numărul de zerglingi produşi de cuibul $i$ într-o oră. Pe linia următoare se vor afla alte $N$ numere $F_i$, reprezentând cuibul care susţine vital cuibul $i$, sau $-1$ în cazul în care cuibul $i$ este autonom.

Date de ieșire

Fişierul de ieşire purification.out va conţine pe prima linie numărul minim de zerglingi rămaşi pe planetă după distrugerea permanentă a tuturor cuiburilor.

Restricții și precizări

• $1 \leq N \leq 2 \ 000$
• $0 \leq W_i \leq 500$
• Se garantează că pot fi distruse permanent toate cuiburile
• Pentru teste în valoare de $10$ puncte, $N \leq 10$
• Pentru teste în valoare de alte $10$ puncte, $N \leq 20$
• Pentru teste în valoare de alte $10$ puncte, $N \leq 50$
• Pentru teste în valoare de alte $10$ puncte, $N \leq 200$

Exemplu

purification.in

6
1 5 3 2 1 50
-1 0 0 1 1 -1

purification.out

95

Explicație

Ordinea optimă de distrugere a cuiburilor este $(5, 0, 1, 2, 3, 4)$. Cuibul $5$ (autonom) este distrus după o oră, deci produce $1 \cdot 50$ zerglingi. Cuibul $0$ (autonom) este distrus după două ore, deci produce $2 \cdot 1$ zerglingi. Cuibul $1$, iniţial, este susţinut vital de cuibul $0$, dar acum este autonom şi este distrus după trei ore, deci produce $3 \cdot 5$ zerglingi. Cuibul $2$ este distrus după patru ore, deci produce $4 \cdot 3$ zerglingi. Cuibul $3$ este distrus după cinci ore, deci produce $5 \cdot 2$ zerglingi. Cuibul $4$ este distrus după şase ore, deci produce $6 \cdot 1$ zerglingi. După ce toate cuiburile au fost distruse, iar producţia de zerglingi a încetat complet, numărul de zerglingi rămaşi este $1 \cdot 50 + 2 \cdot 1 + 3 \cdot 5 + 4 \cdot 3 + 5 \cdot 2 + 6 \cdot 1 = 95$.