题目描述

给定 $n$ 个点，编号为 $1$ 到 $n$，这些结点通过 $n-1$ 条边构成一棵树，$1$ 号点为根。

小爱有一把剪刀，可以剪开树上的任何边。当一条边被剪开后，与根分离的部分就会掉落，根所在的部分将继续保留。剪开不同的边需要花费不同的能量。

给定一个目标 $t$，请问最少应该剪开哪些边，才能让这棵树恰好留下 $t$ 个点，且花费的能量之和最小？

输入格式

• 第一行：两个整数 $n$ 和 $t$。
• 第二行到第 $n$ 行：第 $i$ 行有两个整数 $p_i$ 和 $c_i$，
  • $p_i$ 表示 $i$ 号点的父亲编号，
  • $c_i$ 表示剪开 $i$ 到 $p_i$ 的这条边所需要花费的能量。

输出格式

• 单个整数：表示恰好保留 $t$ 个点所需最少的能量之和。

5 3
1 100
1 10
2 3 
3 5

8

样例解释 1

将4和5切掉，所用费用为3+5

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 50$
• 对于 $60\%$ 的数据，$1\leq n\leq 500$
• 对于 $100\%$ 的数据，$1\leq n\leq 5000$，$1\leq t<n$, $1\leq p_i<i$，$1\leq c_i\leq 10^5$。