#DP0305. 没有上司的舞会3

没有上司的舞会3

题目描述

一家公司里有 nn 个员工,除了公司 CEO 外,每个人都有一个直接上司。今天公司要办一个舞会,为了大家玩得尽兴,如果某个员工的直接上司来了,他/她就不想来了。第 ii 个员工来参加舞会会为大家带来 aia_i 点快乐值。由于场地有大小限制,场地最多只能容纳 mm 个人。请求出快乐值最大是多少。

输入格式

第一行一个整数 n,mn,m

接下来一行,n1n−1 个整数 f2,f3,,fnfi(1fi<i)f_2,f_3,…,f_n,f_i(1≤f_i<i) 表示第 ii 个员工的上司。其中1号点为CEO,没有上司。

接下来一行,nn 个整数 a1,a2,,ana_1,a_2,…,a_n

表示每个员工的快乐值。

输出格式

一行一个整数,表示答案。

Samples

5 2
1 2 3 1
1 8 10 8 2
16

数据规模

对于所有数据,保证 2n5000,0mn,1ai1000002≤n≤5000,0≤m≤n,1≤a_i≤100000