题目描述

有 $N$ 门课，编号为 $1$ 到 $N$。

每门课有一个先修课程，第 $i$ 门课程的先修课程为 $P_i$。意思是如果要修 $i$，必须先修 $P_i$。如果 $P_i = 0$，说明这门课没有先修课程。

如果选择修第 $i$ 门课程，可以获得 $A_i$ 分。给定一个整数 $M$，表示最多只能选修 $M$ 门课，请问应该修哪些课程，才能让得分达到最大，输出这个最大值。

输入格式

• 第一行：两个整数表示 $N$ 与 $M$
• 接下来有 $N$ 行：每行两个整数表示 $P_i$ 与 $A_i$

输出格式

5 3
0 50
1 20
1 30
0 50
4 100

200

数据范围

• $30\%$ 的数据，$1\leq M\leq N\leq 20$
• $60\%$ 的数据，$1\leq M\leq N\leq 300$
• $100\%$ 的数据，$1\leq M\leq N\leq 5000$
• $0\leq A_i\leq 10,000$