Halloween Kemonomimi Party 2014
Problem D: Fox Girls
This morning, you woke up and realized that some foxen have turned into girls! In light of this exciting event, you have kindly invited Izuna, a fox-girl, over to your house (with only pure intentions, of course). You have some anime that you want to share with Izuna, but your list of anime is very long. Therefore, you will adopt the strategy of watching some anime with Izuna while she's at your house, and then leaving with her a list of recommendations.
For each anime in your list, you will recommend to Izuna another anime from that if she has watched one at your house, she should definitely watch the other sometime later. Being an obedient fox-girl, Izuna will always follow your recommendations.
Of course, you have to start watching some anime with Izuna at your house in order for her to follow all the recommendations and eventually watch them all, but since you are short on time, you need to determine the minimum number of minutes you spend watching anime at your house before Izuna can follow some of the recommendations and eventually watch all the anime in the list.
Input Format
The first line of input will have N (2 ≤ N ≤ 100000), the number of anime in your list, numbered from 1 to N.
The second line of input will have N space-separated integers, the time it takes in minutes to watch the i-th anime (1 ≤ timei ≤ 109).
The third line of input will have N space-separated integers, meaning that you recommend the i-th anime if Izuna watched the anime with the i-th number in this list at your house, and vice versa (1 ≤ recommendationi ≤ N, recommendationi ≠ i).
Test cases worth 25% of the marks will have 2 ≤ N ≤ 20.
Test cases worth another 25% of the marks will have 2 ≤ N ≤ 5000.
Of the aforementioned cases, 50% of those will have timei = 1 (1 ≤ i ≤ N).
Output Format
The first and only line of output should be the minimal number of minutes spent watching anime so that Izuna will eventually finish watching all the anime on your list.
Sample Input 1
3 20 23 42 2 3 1
Sample Output 1
20
Explanation 1
By taking 20 minutes to watch the first anime, Izuna will definitely watch the other two anime due to the recommendations.
Sample Input 2
4 100 23 23 24 2 3 1 1
Sample Output 2
47
Explanation 2
Although watching just the first anime is enough for Izuna to watch the rest of the anime on her own, that will take 100 minutes. It is much more efficient to watch the fourth anime and either the second or third anime at your house for a total of 47 minutes.
All Submissions
Best Solutions
Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Nov 04, 2014
Author: FatalEagle
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
rrrrrrrrread this