题目描述

curimit 知道陶陶很喜欢吃苹果。于是 curimit 准备在陶陶生日的时候送给他一棵苹果树。
curimit 准备了一棵这样的苹果树作为生日礼物：这棵苹果树有 $n$ 个节点，每个节点上有 $c_i$ 个苹果，这棵树高度为 $h$。
可是，当 curimit 把这棵树给陶陶看的时候，陶陶却说：“今年生日不收礼，收礼只收节点数减高度不超过 $k$ 的苹果树。”这下 curimit 犯难了，curimit 送来的树枝繁叶茂，不满足节点数-高度 $\leq k$。于是 curimit 决定剪掉一些枝条，使得修剪过后的树满足节点数减高度 $\leq k$，但是 curimit 又想保留尽量多的苹果数目。curimit 想请你帮他算算经过修剪后的树最多能保留多少个苹果。

注：

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

输入格式

输入文件的第一行为两个整数 $n,k$ 分别表示这棵树有 $n$ 个节点，修剪后的树节点数减高度 $\leq k$。
第二行开始到第 $n+1$ 行，每行有两个数，第 $i+1$ 行的两个数 $father_i$ 和 $c_i$ 分别表示节点 $i$ 的父亲是 $father_i$ 和节点 $i$ 处有 $c_i$ 个苹果。

规定：节点 1 的父亲为 0。

输出格式

输出文件仅包含一行，表示在满足修建后的树节点数减高度 $\leq 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 \leq 10$。
对于 $30\%$ 的数据，$n \leq 100$，$0 \leq k \leq 20$。
对于 $100\%$ 的数据，$n \leq 4000$，$0 \leq k \leq 500$。

题目来源

Vijos1676