Minimum Modification Cost for Rating Consistency

ID: 20757

Type: Default

1000ms

256MiB

B Taro is a journalist who primarily covers OI competitions. With the upcoming IOI, he has collected interview information from n contestants. Each contestant is numbered from 1 to n and has a rating in the range $[1,10^9]$. From the interviews, he learned that for every contestant $i$ ($1\le i\le n$), the rating of contestant $i$ is at least as high as the rating of contestant $a_i$ (where $1\le a_i\le n$); note that $a_i$ may be equal to $i$.

Later, B Taro received an official rating table from the system’s administrator, which shows that the rating of contestant $i$ is $h_i$. However, the table might contain errors which make it inconsistent with the interview information.

To meet his deadline, B Taro decides to change some ratings in the table. Changing the rating of contestant $i$ costs $c_i$ yen. When modifying a rating, he may assign any integer value between 1 and $10^9$ to that contestant.

Your task is to determine the minimum total cost needed to modify the rating table so that for every contestant $i$, the following condition holds:

[ x_i \ge x_{a_i}, \quad \text{for } 1\le i \le n, ]

Here $x_i$ is the final rating of contestant $i$. For contestants whose ratings are not modified, $x_i$ remains equal to $h_i$. For a pair $i$ and $a_i$ with $h_i < h_{a_i}$, if neither rating is changed then the constraint is violated; however, if at least one of them is modified, B Taro can assign appropriate values to ensure $x_i \ge x_{a_i}$.

Input/Output Example: Suppose there is an edge (i, a_i) for which $h_i < h_{a_i}$. Then, to satisfy the condition, at least one of the two contestants must have their rating changed. The goal is to find a set of contestants to modify (paying the corresponding costs) so that all such constraints are covered, while the total cost is minimized.

inputFormat

The first line contains a single integer n (the number of contestants).

The second line contains n integers $a_1, a_2, \ldots, a_n$, where for each contestant $i$, the interview tells us that contestant $i$'s rating is at least that of contestant $a_i$.

The third line contains n integers $h_1, h_2, \ldots, h_n$, where $h_i$ is the current rating of contestant $i$ on the table.

The fourth line contains n integers $c_1, c_2, \ldots, c_n$, where $c_i$ is the cost to modify contestant $i$'s rating.

outputFormat

Output a single integer, the minimum total cost (in yen) required to adjust the rating table so that the condition $x_i \ge x_{a_i}$ holds for every $i$.

sample

#P7563. Minimum Modification Cost for Rating Consistency

Minimum Modification Cost for Rating Consistency