Task DescriptionDiscussion (0)

From the first line of the standard input read an integer

To the standard output write one integer representing the maximal value of presents mister Little Z can get at his imaginary party

Task :: z-company

Mister Little Z sometimes imagines that z-trening is a big company with a lot of employees with a pyramidal structure (Big Boba is the main boss, and every employee has its own boss).

One day Little Z was planning a party for his imaginary employees. Little Z know the value of presents each of the employees would bring to the party. However, due to the crisis the employee-boss relations in the company are not very good, so Z wants to invite only some of the employees so that:

- No employee and his boss are at the party

- He maximizes the value of the presents brought to the party

One day Little Z was planning a party for his imaginary employees. Little Z know the value of presents each of the employees would bring to the party. However, due to the crisis the employee-boss relations in the company are not very good, so Z wants to invite only some of the employees so that:

- No employee and his boss are at the party

- He maximizes the value of the presents brought to the party

**INPUT:**

From the first line of the standard input read an integer

**N**(1 <=

**N**<= 100000). The employee with index 0 is Big Boba - the main boss. From the next (second) line read one integer

**V**representing the value of the present that Big Boba would bring to the party. From the next

**N-1**lines read the information about the rest

**N-1**employees, from each of the two lines read two integers

**B**and

**V**, where

**B**is the 0-based index of the corresponding employee, and

**V**is the value of the present they would bring to the party. We have 0 <=

**B**<

**N**and 1 <=

**V**<= 1000000.

**OUTPUT:**

To the standard output write one integer representing the maximal value of presents mister Little Z can get at his imaginary party

Input:

Output:

Explanation employees with indices 1 and 3 would be invited

**4**

1

0 2

0 1

2 2

1

0 2

0 1

2 2

Output:

**4**

Explanation employees with indices 1 and 3 would be invited

Input:

Output:

Explanation employees with indices 0, 3 and 4 would be invited

**5**

1

0 2

0 1

1 2

2 2

1

0 2

0 1

1 2

2 2

Output:

**5**

Explanation employees with indices 0, 3 and 4 would be invited

Submit Solution

Available Languages

Task info

Name: | z-company |

Time: | 0.25 sec. |

Memory: | 16 MB |

#Tests: | 10 |

AddedBy: | admin |

Task Ratings

Difficulty: | 3.9 (9 votes) |

Quality: | 3.7 (9 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

bl4ck.c0d3r | 0.13 s. |

ivan100sic | 0.133 s. |

Al3kSaNdaR | 0.139 s. |

vdmedragon | 0.151 s. |

halil | 0.163 s. |

tsebayoth | 0.166 s. |

PetarV | 0.167 s. |

zare2000 | 0.17 s. |

ortschun | 0.178 s. |

frank44 | 0.178 s. |

Solved By