瞬(teleport)
你要遍历一棵以 $1$ 为根的 $n$ 个节点的外向树，你走过一条边需要一定的时间。另外，你可以在节点放置分身，你可以瞬移到任何一个分身处；同时，你可以在任何时候收走一个点上的分身。整个树最多同时存在 $k$ 个分身。求最小时间。
输入格式
第一行两个整数 $n,p$ 表示树的大小及最多同时存在的分身数的范围。
接下来 $n-1$ 行中，第 $i$ 行两个整数 $f$ 和 $t$ 表示 $i$ 的 父亲节点编号以及走过 $i$ 的父亲到 $i$ 这条边所需时间。
输出格式
$p$ 行，第 $i$ 行一个整数表示当 $k=i$ 时的最小时间。
数据范围
Subtask1(10%) $n\le 10$
Subtask2(20%) $n\le 20$
Subtask3(30%) $n\le 100$
Subtask4(20%) $p\le 20$
Subtask5(20%) $n\le 1000$
对于所有数据，满足 $1\le p\le n\le 1000,1\le t\le 10^9$，且每个点父亲节点编号小于该点编号。