题目描述

脚踩油门，轮胎尖叫，警笛长鸣。紧急车辆会不惜一切代价以最快的速度到达目标地点。时间至关重要，因为往往关乎生命。

提供紧急服务始终是一个挑战，特别是在像哈萨克草原这样人口稀疏的地区。相比所服务的少量人口，建设基础设施的成本非常高。因此，尽量减少道路数量和车辆数量非常重要。另一方面，尽可能缩短紧急服务的响应时间也是至关重要的。

本题考虑一个已经将道路数量最小化的路网，这意味着任意两个村庄之间有且仅有一条路径相连。多亏了政府拨款，哈萨克草原消防部门最近购置了一些崭新的消防车。该部门希望在一些村庄建立消防站，并将消防车分配到这些消防站，以优化保证的响应时间。

你的任务是找到一个最优的消防车放置方案，使任何村庄都能在最短的时间内被消防车到达。你可以忽略召集消防队员和启动消防车所需的时间，以及穿越村庄所需的时间。响应时间仅由沿道路行驶的时间决定。

输入格式

第一行包含两个整数：村庄数量 $n$ $(1 \leq n \leq 100\,000)$ 和消防车数量 $f$ $(1 \leq f \leq n)$。

接下来有 $n-1$ 行，编号从 $2$ 到 $n$。第 $i$ 行包含两个整数 $v_{i}$ $(1 \leq v_{i} < i)$ 和 $t_{i}$ $(1 \leq t_{i} \leq 10\,000)$，表示村庄 $i$ 和村庄 $v_{i}$ 之间有一条双向道路，行驶时间为 $t_{i}$。

输出格式

输出通过将消防车放置在 $f$ 个村庄中可以保证的最小响应时间。

样例 1

输入

6 2
1 8
2 7
2 7
3 6
3 5

输出

8

样例 2

输入

3 3
1 1000
2 1000

输出

0