题目描述

• 有一棵 $n$ 个点、根为 $1$ 的树。第 $i$ 个点上有 $c_i$ 个物品，权值均为 $v_i$。
• 需要先选择 $t$ 个不同的点，对于选的每个点，在它的每个祖先（包括自己）上各取一个物品。
  • 本题保证 $\boldsymbol{t \lt c_i}$，因此不会存在没有物品可取的情况。
• 接下来可以取至多 $k$ 个物品，要求所有在这一步被取了物品的点形成一个含根的连通块。
• 最大化整个过程中取的物品权值之和。

输入格式

• 第一行三个整数 $n, k, t$。
• 接下来 $n$ 行，每行两个正整数分别表示 $c_i$ 和 $v_i$。
• 最后一行 $n - 1$ 个正整数，第 $i$ 个正整数表示点 $(i + 1)$ 在树上的父亲 $\mathrm{fa}_{i + 1}$。

输出格式

• 一行，输出一个非负整数，表示最大的权值和。

样例

样例 1 输入

4 4 1
2 1 
2 1
2 5
2 1
1 1 2

样例 1 输出

15

数据范围

对于所有数据：$1 \leq n, k \leq 10^4$，$0\leq t \leq n$，$\boldsymbol{t \lt c_i} \leq 10^9$，$1\leq v_i \leq 10^9$，$\mathrm{fa}_i \lt i$，$nk(t+1)\leq 10^7$。

• 子任务 1（10 分）：$n, k, t \leq 10$。
• 子任务 2（20 分）：$t = 0$。
• 子任务 3（15 分）：$n k (t + 1) \leq 10^6$。
• 子任务 4（25 分）：$n k (t + 1) \leq 5 \times 10^6$。
• 子任务 5（30 分）：无特殊限制。