19416번 - Lines Game 다국어

Consider the following game about removing $N$ straight line segments on the plane. The segments are numbered from $1$ to $N$. The $i$-th segment connects points $(0, i)$ and $(1, p_i)$, where the numbers $p_1, p_2, \ldots, p_N$ are a permutation of numbers from $1$ to $N$. Your are also given $N$ positive integers $v_1, v_2, \ldots, v_N$. On each step, you can select any segment $i$ which is not removed yet, pay $v_i$ dollars, and then remove the $i$-th segment and all segments intersecting with it. Note that you MUST remove all segments which intersect with $i$-th segment.

The purpose of this game is to remove all segments while spending the minimum possible sum of dollars. Please answer how much you need to spend when you play the game with best strategy.

The input consists of three lines. The first line contains an integer $N$. The second line consists of $N$ integers $p_1, p_2, \ldots, p_N$. The third line consists of $N$ integer $v_1, v_2, \ldots, v_N$.

Output only one number indicating the minimum possible sum of dollars required to remove all segments.

• $1 \le N \le 10^5$
• $\langle p_i \rangle$ is a permutation of $1, 2, \ldots, N$
• $1 \le v_i \le 2 \times 10^4$