Filiki Etairia

We are in Odessοs in 1814, witnessing the establishment of the Filiki Etairia. The preparation for the upcoming revolution requires absolute secrecy, so the members of Filiki Etairia devised the following system:

Filiki Etairia consists of N members.

Each member uses a pseudonym, which is a different integer from ~1~ to N. The oldest member (let's call him "First") uses the pseudonym ~1~.

Each Filikos u, except the First, has been invited to join the Filiki Etairia by an older Filiko p_u. In order to be informed about the news of Filiki Etairia, u receives an encrypted letter from p_u. The time required to decrypt it is t_u minutes.

When a secret needs to be spread, for security reasons, the First initially discloses it only to K-1 other Filikous, so that a total of K (including himself) initially know it. These K (along with the First) simultaneously send letters to those Filikous they have invited, who, in turn, decrypt the letter they received and then send it to those they have invited, and so on.

Based on the above secrecy system, the First asks you to design a program that optimally selects the K-1 Friendlies to whom he will initially reveal the secret, in order to minimize the time required for the secret to be known to all members through the above process.

Problem:

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the values of N, K, as well as the values of p_u and t_u for each member except the First. Print the minimum possible time in which a secret can be disclosed to all members.

Input File:

The input file named filiki.in is a text file with the following structure. The first line contains two integers separated by a space: the total number N of all Filikous, and the number K of Filikous from which the secret starts spreading. Followed by N-1 lines that correspond in order to the members u except the First (2 ≤ u ≤ N). Each such line contains two integers separated by a space: the member p_u who invited the member u to the Filiki Etairia, and the time t_u that member u needs to decrypt a letter.

Output File:

The output file named filiki.out is a text file that contains a single line with an integer: the minimum possible time in which a secret can be disclosed to all members if the First selects the K-1 Filikous optimally.

Examples of input - output files:

1st

STDIN (filiki.in)

5 2
1 50
1 10
3 25
4 20

STDOUT (filiki.out)

50

Explanation: Here, K=2, so the First must choose one more Friendly to initially disclose the secret to. Let's say he chooses 5. Immediately, 1 sends the secret to those he invited (2 and 3), while 5 does not send it anywhere since he did not invite anyone. In 10 minutes, 3 has decrypted the letter and forwards it to 4. In another 25 minutes (thus at minute 35), 4 decrypts his letter. Finally, at minute 50, 2 decrypts the letter he received from 1. Therefore, in a total of 50 minutes, everyone knows the secret. There is no better choice that leads to a shorter overall time.

2nd

STDIN (filiki.in)

5 3
1 50
1 10
3 25
4 20

STDOUT (filiki.out)

20

Explanation: The same example as before, with the difference that now K=3. This time, the First can choose 2 and 4. 3 receives a letter from 1, which he decrypts in 10 minutes, and 5 receives a letter from 4, which he decrypts in 20 minutes. Therefore, in 20 minutes, everyone knows the secret. There is no better choice than this.

Constraints:

• 1 ≤ K ≤ N ≤ 200.000
• For each Filiko u except the First, it will be 1 ≤ p_u < u
• 1 ≤ t_u ≤ 100
• For test cases with a total value of 10%, 1 ≤ N ≤ 25, and no Filikos will have invited more than 2 members.
• For test cases with a total value of 30%, 1 ≤ N ≤ 150, and no Filikos will have invited more than 2 members.
• For test cases with a total value of 50%, 1 ≤ N ≤ 150.

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.