Vijos1676 陶陶吃苹果

curimit 知道陶陶很喜欢吃苹果，于是准备在陶陶生日的时候送给他一棵苹果树。

curimit 准备的苹果树是这样的：这棵树有 $n$ 个节点，第 $i$ 个节点上有 $c_i$ 个苹果，整棵树的高度为 $h$。

可是，当 curimit 把这棵树给陶陶看的时候，陶陶却说：「今年生日不收礼，收礼只收节点数减高度不超过 $k$ 的苹果树。」

这下 curimit 犯难了：他送来的树枝繁叶茂，并不满足节点数 $-$ 高度 $\le k$。于是 curimit 决定剪掉一些枝条，使得修剪过后的树满足节点数 $-$ 高度 $\le k$，同时又想保留尽量多的苹果。请你帮他算算经过修剪后的树最多能保留多少个苹果。

注意：

1. 节点 $1$ 为树根，不能把它剪掉；
2. 只有 $1$ 个节点的树，高度为 $1$。

输入格式

第一行两个整数 $n, k$，分别表示这棵树有 $n$ 个节点，以及修剪后的树需要满足节点数 $-$ 高度 $\le k$。

第 $2$ 行到第 $n+1$ 行，每行两个数。第 $i+1$ 行的两个数 $\mathrm{father}_i$ 和 $c_i$ 分别表示节点 $i$ 的父亲是 $\mathrm{father}_i$，以及节点 $i$ 处有 $c_i$ 个苹果。规定节点 $1$ 的父亲为 $0$。

输出格式

仅一行一个整数，表示在满足修剪后的树节点数 $-$ 高度 $\le k$ 的条件下，最多能保留的苹果数。

样例输入

10 3
0 89928
1 38219
1 91615
2 5517
3 15244
3 78458
1 76512
4 99582
7 64607
1 91175

样例输出

494494

数据范围

• 对于 $10\%$ 的数据，$n\le 10$；
• 对于 $30\%$ 的数据，$n\le 100$，$0\le k\le 20$；
• 对于 $100\%$ 的数据，$n\le 4000$，$0\le k\le 500$。

来源与许可

本题题面与测试数据整理自 BZOJ 2645。

样例 1

输入

10 3
0 89928
1 38219
1 91615
2 5517
3 15244
3 78458
1 76512
4 99582
7 64607
1 91175

输出

494494