油门踩到底。轮胎尖叫。警笛长鸣。紧急救援车辆必须尽一切必要手段尽快到达目标地点。时间至关重要，因为生命往往系于一线。

在哈萨克斯坦草原等人口稀少的地区，提供紧急服务总是充满挑战。与所服务的人口数量相比，基础设施建设的成本很高。因此，在尽量减少道路数量和车辆数量的同时，最大限度地缩短紧急服务的响应时间也至关重要。

本题考虑的道路网络已经实现了道路数量的最小化，这意味着任意两个村庄之间都恰好有一条路径相连。得益于政府拨款，哈萨克斯坦草原消防局最近购置了一些崭新的消防车。消防局希望在部分村庄建立消防站，并以一种优化保证响应时间的方式分配这些消防车。

你的任务是找到一种最优的消防车部署方案，使得任意村庄到达最近消防车的响应时间最小化。你可以忽略集结消防队员和启动车辆所需的时间，以及穿过村庄本身所需的时间。响应时间仅由在道路上的行驶时间决定。

哈萨克斯坦草原，图片来源：Carole via Wikimedia Commons, CC BY-SA 3.0

输入格式

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

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

输出格式

输出通过在 $f$ 个村庄部署消防车所能保证的最小响应时间。

样例

样例输入 1

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

样例输出 1

8

样例输入 2

3 3
1 1000
2 1000

样例输出 2

0