[R3E]知识点学习 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 个知识点，编号从 $1$ 到 $n$，知识点 $i$ 的价值为 $a_i$。

想学习知识点 $i$，必须先学习知识点 $p_i$，我们称 $p_i$ 是 $i$ 的前置知识点。保证 $p_i< i$，如果 $p_i=0$ 说明知识点 $i$ 可以直接学习。

求学习恰好 $m$ 个知识点的最大价值和。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示知识点的数量和打算学习的知识点的数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每个知识点的价值。

第三行包含 $n$ 个整数 $p_i$，分别表示每个知识点的前置知识点。

输出格式

输出一个整数，表示学习恰好 $m$ 个知识点的最大价值和。

样例

样例输入 #1

6 3
4 2 5 4 1 10
0 1 0 3 1 5

样例输出 #1

15

数据规模

对于 $20\%$ 的数据， $n\leq 20$。

对于 $60\%$ 的数据， $n\leq 200$。

对于 $100\%$ 的数据， $1\leq m\leq n\leq 5000$， $1\leq a_i\leq 10^9$，$0\leq p_i< i$。