32428번 - Steppe on It 다국어

문제

The gas pedal on the floor. Squealing tires. Wailing sirens. Emergency vehicles do whatever is necessary to reach their target locations as quickly as possible. Time is critical because lives often depend on it.

Providing emergency services is always challenging, especially for sparsely populated areas such as the Kazakh Steppe. The cost of building infrastructure is high compared to the number of people served. It is therefore important to minimize both the number of roads and the number of vehicles. On the other hand, it is also vital to minimize the response time of emergency services.

This problem considers a road network that already minimizes the number of roads, which means that any two villages are connected by exactly one path. Thanks to a government grant, the Kazakh Steppe Fire Department recently acquired some shiny new fire engines. The department wants to establish fire stations in some of the villages and allocate the fire engines to them in a way that optimizes the guaranteed response time.

Your task is to find an optimal placement of fire engines that minimizes the time needed for any village to be reached by a fire engine. You can neglect the time needed to assemble the fire crew and start the engine as well as the time to travel across any villages. The response time is determined solely by traveling along the roads.

입력

The first line contains two integers: the number of villages $n$ (1ドル ≤ n ≤ 100,円 000$) and the number of fire engines $f$ (1ドル ≤ f ≤ n$).

This is followed by $n-1$ lines numbered from 2ドル$ to $n$. Line number $i$ contains two integers $v_i$ (1ドル ≤ v_i < i$) and $t_i$ (1ドル ≤ t_i ≤ 10,円 000$) meaning that there is a two-way road between villages $i$ and $v_i$ that can be traveled in time $t_i$.

출력

Output the minimum response time that can be guaranteed by placing fire engines into $f$ villages.

제한

힌트