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
InputFrom 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.
OutputTo 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 2Output:
4Explanation 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 2Output:
5Explanation employees with indices 0, 3 and 4 would be invited
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.