Banja i Voža su se konačno obogatili. Vlasnici su korporacije Makrohard koja se u
poslednje vreme pokazala kao neprikosnoveno najbolja u polju razvoja operativnih sistema
i internet servisa. Makrohard je organizovan u vidu n poslovnica koje se nalaze u strogoj
hijerarhiji. Poslovnica 1 je sedište korporacije i ona je, direktno ili indirektno (preko
drugih poslovnica), nadređena svim ostalim. Svaka druga poslovnica ima tačno jednu direktno
nadrešenu koja ima redni broj manji od nje. Vrednosti svih poslovnica su zadate u
milionima dolara.
Na žalost, kako to obično biva, Banja i Voža su se posvašali oko dizajna zvanične
šolje za kafu korporacije i odlučili da više ne mogu da posluju zajedno. Srećom, njihova
dugogodišnja poznanica, a sada kontroverzni biznismen, Tana Rišović odlučila je
da kupi Makrohard i tako pomogne Banji i Voži da se rastanu pre nego što dođe do većih
incidenata. Međutim, svi znamo da milionske transakcije nikada nisu jednostavne i da ih,
ukoliko ne želimo da veliki deo novca završi u rukama Poreske uprave, moramo pažljivo
planirati.
Tanin računovođa je zaključio da, kako bi ukupan porez bio što manji, Tana svakog meseca
treba da kupi tačno jednu poslovnicu Makroharda zajedno sa svim ostalim kojima je ona
nadređena (direktno ili indirektno) a koje već ne poseduje, i pritom potroši najviše k
miliona dolara. Vaš zadatak je da pomognete Tani tako što ćete izračunati minimalno
trajanje ove transakcije.
Ulaz.
(Ulazni podaci se učitavaju iz datoteke porez.in.)
U prvom redu ulazne datoteke nalaze se prirodni brojevi n (1 ≤ n ≤ 100.000)
i k (1 ≤ k ≤ 230) - broj poslovnica firme Makrohard i količina novca koju
Tana može da potroši svakog meseca. U sledećem redu nalazi se n prirodnih brojeva razdvojenih razmacima -
qlanovi niza V , gde Vi predstavlja vrednost svake od poslovnica u milionima
dolara (Vi ≤ 230).
U trećem redu nalazi se n - 1 prirodan broj - članovi niza A, gde Ai
predstavlja redni broj direktno nadređene poslovnice za poslovnicu i + 1 (Ai ≤ i).
Izlaz.
(Izlazni podaci se ispisuju u datoteku porez.out)
U prvom i jedinom redu izlazne datoteke ispisati jedan ceo broj - najmanji broj mesečnih
transakcija potreban da bi se prodaja Makroharda okončala.
Primer 1.
porez.in
|
|
porez.out
|
6 20
7 6 7 5 6 4
1 1 2 4 4
|
|
2
|
Objašnjenje.Tana će u prvom mesecu kupiti poslovnice 4,5 i 6, a u drugom 1,2 i 3.
Napomena.
Transakcija će uvek moći da se obavi.