Egy vállalat $N$ embert foglalkoztat. Mindenkinek legfeljebb két beosztottja (akiknek a sorrendje nem fontos), és pontosan egy felettese van, kivéve a főigazgatót, akinek nincs felettese. A munkatársakat az $\mathrm{1,}\text{...}\mathrm{,}N$ számokkal azonosítjuk, az 1-es a főigazgató. A cég súlyos pénzügyi gondokkal küzd, ezért elhatározták, hogy átszervezik a beosztás rendszerét. Ehhez felvehetnek új munkatársakat, illetve megválhatnak bizonyos alkalmazottaktól. Ezenkívül az egyedüli megengedett művelet az azonosítószámok átírása. Minden egyes új munkatárs felvételéhez állásinterjút kell szervezni $F$ krajcárért, valamint tudjuk, hogy az $i$-edik alkalmazott elbocsátása a végkielégítés miatt $V\left[i\right]$ krajcárba kerül. Az azonosítók átírásának természetesen nincs költsége.
A cégvezetés megadta, hogy szerintük mi az optimális vállalati struktúra. A fenti feltételek erre a szerkezetre is igazak. Írjunk programot, ami megadja, hogy legalább hány krajcárt kell elkölteni az átalakításra.
A standard bemenet első sora az alkalmazottak $N$ számát és egy új alkalmazott felvételének $F$ költségét tartalmazza. A második sor $N$ egész számot tartalmaz, az $i$-edik szám $V\left[i\right]$, vagyis az $i$-edik alkalmazott végkielégítése. A harmadik sor $N-1$ számot tartalmaz, az $i$-edik szám az $\left(i+1\right)$-edik beosztott felettesének a száma. A negyedik és ötödik sor az átalakítás után elérni kívánt struktúrát írja le: a negyedikben az alkalmazottak kívánt $M$ száma található, míg az ötödikben $M-1$ egész szám írja le a feletteseket a harmadik sorhoz hasonló módon.
A standard kimenet első és egyetlen sora tartalmazza az átalakítás minimális $K$ költségét.
Korlátok: $1\le N$, $M\le 5000$; $0\le V\left[i\right]$, $F\le {10}^5$; időlimit: 0,2 mp; memórialimit: 256 MB.
A verem (stack) méretére nincs külön korlát, ez is a teljes memóriába számít bele.