Map of Tasks

Time limit: 0.15s Memory limit: 32MB Input: Output:

Giorgio’s high-school in Italy is serious about the IIOT: all its the students are training for the next edition of the contest, and they absolutely want to earn their school a medal. The head Computer Science professor of the school has prepared a detailed training program for his students: a map of all the tasks that should be fully solved in order to be ready for the competition.

The map is given as a rooted tree with NN nodes (numbered from 00 to N1N - 1) where each node represents a task, and the parent-child relationships represent restrictions in the order in which the tasks should be solved. More specifically: if a task uu has a task vv among its children, this means that the task uu should be solved first in order to “unlock” the task vv.

The students know, for each task uu, the time TuT_u (in hours) that it would take a single student to solve the task with no external help. Because of how the map is made, these tasks can be attempted in parallel: multiple tasks can be attempted at the same time by different students, however it’s not possible for multiple students to work on the same task.

Help the students calculate the minimum amount of hours that it will take them to solve all the tasks in the map. But wait! To make things more interesting, the professor agreed that the students can “cheat” a maximum of CC times: this means that for CC tasks they will be able to simply find a solution online, spending 00 hours on those tasks.

Input data

The first line contains two integers NN and CC, the total number of tasks in the map and the number of tasks that students are allowed to solve by “cheating”. The next NN lines describe the tasks: the ii-th line (with ii going from 00 to N1N - 1) contains two integers PiP_i and TiT_i, which indicate that:

  • Before solving task ii, a student must solve task PiP_i. If PiP_i = 1-1, then task ii is the root of the map and it’s the first task to solve.
  • Solving task ii without any help will take a student TiT_i hours.

Output data

You need to write a single integer: the minimum number of hours that the students will need to solve all the tasks.

Constraints and clarifications

  • 1N10 0001 \leq N \leq 10 \ 000.
  • 0C1000 \leq C \leq 100.
  • 0Ti1090 \leq T_i \leq 10^9 for each i=0N1i = 0 \leq N - 1.
  • Pi=1P_i = -1 for exactly one value of ii, and 0Pi<N0 \leq P_i < N for all other values of ii.
  • Following the iPiPPii \rightarrow P_i \rightarrow P_{P_i} \rightarrow \dots chain always leads to the root of the tree, for each i=0N1i = 0 \dots N - 1.
  • The school has enough students to tackle as many tasks in parallel as needed.
# Score Constraints
1 0 Examples
2 18 N15N \leq 15
3 9 C=0C = 0
4 23 C=1C = 1
5 29 C20C \leq 20
6 21 No additional limitations.

Example 1

stdin

5 2
3 10
4 1
3 5
-1 20
3 2

stdout

5

Explanation

The first sample case is shown on the right: there are 55 tasks and only 22 of them can be skipped. Skipping task 00 and task 33 leads to the optimal solution, whose total time is 55 hours. After skipping task 33 (the root), task 44 and 22 can be tackled in parallel; after 22 hours task 44 is solved and task 11 can be started.

After 55 hours, task 22 is solved and you cannot choose another set of tasks to skip to reduce this time.

Example 2

stdin

7 2
1 10
-1 1
3 10
1 3
1 7
0 7
5 9

stdout

14

Explanation


The second sample case has 77 tasks and only 22 of them can be skipped. A possible optimal solution is shown on the right, reducing the total time down to 1414 hours.

Log in or sign up to be able to send submissions!