시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB135538.462%

문제

Bliže se lokalni izbori!

Prije promjene vlasti potrebno je podijeliti bonuse u jednom neimenovanom odjelu gradske uprave. Hijerarhiju uprave možemo predstaviti stablom u kojem je čvor $1$ označen kao direktor, a izravni šef svakog zaposlenika je njegov roditelj u stablu.

Ako $i$-ti zaposlenik dobije bonus u iznosu od barem $c_i$, njegova će se produktivnost u sljedećoj godini povećati za $p_i$, dok u suprotnom ostaje nepromijenjena. Nije nužno da svi zaposlenici dobiju bonus, ali za svakog zaposlenika koji dobije bonus mora vrijediti da je i njegov izravni šef dobio barem neki pozitivan bonus (makar u iznosu $1$).

Odredite najveće moguće povećanje ukupne produktivnosti odjela ako je ukupan iznos proračuna za bonuse najviše $K$.

입력

U prvom retku su prirodni brojevi $N$ i $K$.

U drugom je retku $N − 1$ brojeva $s_i$ ($1 ≤ s_i ≤ i$) gdje $i$-ti broj označava izravnog šefa $i + 1$-tog radnika.

U trećem je retku $N$ brojeva $p_1, p_2, \dots , p_N$.

U četvrtom je retku $N$ brojeva $c_1, c_2, \dots , c_N$.

출력

U jedini redak ispišite najveće moguće povećanje produktivnosti uz zadani proračun.

제한

U svim podzadacima vrijedi $2 ≤ N ≤ 5\, 000$ i $1 ≤ K ≤ 5\, 000$.

Za sve $i = 1, \dots , N$ vrijedi da je $1 ≤ p_i ≤ 10^5$ i $1 ≤ c_i ≤ 5\, 000$.

서브태스크

번호배점제한
17

$N ≤ 20$

29

$c_i = 1$ za sve $i$ i dodatno ako je $j$ šef od $i$ tada $p_j ≥ p_i$.

314

Za sve $i < N$, izravan šef od $i + 1$ je $i$.

419

$N, K ≤ 500$

521

$N ≤ 100$

630

Nema dodatnih ograničenja.

예제 입력 1

2 100
1
10 10
101 100

예제 출력 1

0

예제 입력 2

5 7
1 1 2 2
2 1 2 3 3
4 2 4 2 3

예제 출력 2

6

예제 입력 3

4 9
1 2 2
3 4 4 2
2 5 5 4

예제 출력 3

7

노트

Pojašnjenje drugog probnog primjera:

Primjer valjane dodjele bonusa je sljedeći: zaposlenici dobiju redom $1$, $1$, $0$, $2$ i $3$ bonusa.

Dodjela $1$, $1$, $1$, $2$, $3$ nije valjana jer ukupni broj dodijeljenih bonusa premašuje dozvoljeni proračun.

Dodjela $0$, $1$, $1$, $2$, $3$ također nije valjana jer je zaposlenik $2$ dobio bonus, a njegov izravni šef nije.

채점 및 기타 정보

  • 예제는 채점하지 않는다.