Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Goblinas

Goblinas Gabijus atrado tikrą lobį - daugybę išmėtytų dėžučių su pinigais. Patrynęs rankomis goblinas jau norėjo jas visas šluoti sau kišenėn, tačiau jį sustabdė mįslingas balsas: "Ne taip greit, Gabijuk! Šios dėžutės yra sujungtos magiškais burtais, todėl visų jų paimti negali!". Po ilgo pokalbio su balsu, goblinas sužinojo, kad šias N dėžučių jungia N-1 magiškas saitas. O magija labai paprasta - jei dėžutes u ir v jungia saitas, tai jos niekaip negali būti vienu metu vienoje vietoje, tad goblinas gali paimti ne daugiau kaip vieną iš jų. Taip pat, balsas pavadino šiuos burtus "medine magija", be tai turbūt nieko nereiškia :).

Mįslingas balsas buvo baisiai malonus ir išdavė goblinui, kurias dėžučių poras jungia magiški saitai. Taip pat, goblinas žino, kad i-ojoje dėžutėje yra c_i pinigų. Dabar belieka viena užduotis - išsirinkti poaibį dėžučių taip, kad suma pinigų, esančių jose, būtų maksimali. Tai padarius liks tik kuo greičiau nešdintis. Deja, dėžučių (o taip pat ir magiškų saitų) yra gana daug, tad goblinui prireikė jūsų pagalbos. Parašykite programą, nustatančią, kiek daugiausiai pinigų goblinas gali išsinešti.

Pradiniai duomenys

Pirmoje eilutėje pateiktas vienas sveikasis skaičius N - dėžučių kiekis (1\\leqN\\leq3\\cdotp10^5).

Antroje eilutėje pateikta N tarpais atskirtų sveikųjų skaičių. i-asis iš jų yra pinigų kiekis i-ojoje dėžutėje c_i (1\\leqc_i\\leq10^9).

Trečiojoje eilutėje pateikta N skaičių, apibūdinančių magiškus saitus. i-asis iš šių skaičių yra p_i. Jei p_i\\geq1, tai dėžutes i ir p_i jungia briauna. Yra garantuota, kad šioje eilutėje bus lygiai vienas nulis.

Rezultatai

Jūsų programa turi išvesti vieną sveikąjį skaičių - didžiausią pinigų sumą, kurią gali surinkti goblinas.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
7
2 1 3 10 5 1 1
0 1 1 2 4 4 4
 
13
 
7
2 1 3 10 5 1 4
0 1 1 2 4 4 4
 
14

Paaiškinimas

Pirmasis pavyzdys atrodo taip:

pirmas pavyzdys

Čia paryškintos dėžutės, kurias goblinui apsimoka imti. Užrašas a(b) reiškia, kad dėžutės numeris yra a, o joje yra b pinigų. Taigi, šiuo atveju goblinui apsimoka imti 3 ir 4 dėžutes ir gauti 3+10=13 pinigų.

Antrasis pavyzdys atrodo taip:

antras pavyzdys

Šiuo atveju goblinui apsimoka imti 2, 3, 5, 6 ir 7 dėžutes ir gauti 1+3+5+1+4=14 pinigų.