403658: GYM101234 E 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₁, p₂, ..., p_N are a permutation of numbers from 1 to N. Your are also given N positive integers v₁, v₂, ..., 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₁, p₂, ..., p_N. The third line consists of N integer v₁, v₂, ..., v_N.

• 1 ≤ N ≤ 10⁵
• is a permutation of 1, 2, ..., N
• 1 ≤ v_i ≤ 2 × 10⁴

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

4
2 1 4 3
1 2 3 4

4

4
1 2 3 4
1 2 3 4

10