svemirci
On some planet there are N living species. Some species make food for themselves from unliving matter, and every other living species eats exactly one type of living species. No species are cannibalistic. All of these species are valuable to scientists, and the value of each species is given as a real positive number. An expedition wants to choose some types of living species to bring back to Earth, but they can't transport them separately. Determine the species that they should take, such that no species would be eaten during the trip and that the sum of the values of the living species that are brought to Earth is as high as possible.
Input:
5
57,153 0
101,120 1
328,111 5
234,543 5
987,654 0
Output:
1088.774
InputThe first line of the standard input contains a number N (N <= 2000), which represents the number of different living species. Each of the next N lines contains two numbers. In row k + 1 (k = 1, ..., N), there is one real positive number (less than 1000, double precision), which represents the value of the k-th species, and another positive whole number, which represents the serial number of the type of species that the k-th type eats. If the species of type k produces food from unliving matter, then the second number in the row k + 1 is 0.
OutputTo the standard output write the maximum total value of species, selected according to these rules. The result should be displayed to 3 decimal places.
Input:
5
57,153 0
101,120 1
328,111 5
234,543 5
987,654 0
Output:
1088.774
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.