403658: GYM101234 E Lines Game

Memory Limit:0 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Lines Gametime limit per test2 secondsmemory limit per test512 mebibytesinputstandard inputoutputstandard output

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, pi), where the numbers p1, p2, ..., pN are a permutation of numbers from 1 to N. Your are also given N positive integers v1, v2, ..., vN. On each step, you can select any segment i which is not removed yet, pay vi 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.

Input

The input consists of three lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN. The third line consists of N integer v1, v2, ..., vN.

  • 1 ≤ N ≤ 105
  • is a permutation of 1, 2, ..., N
  • 1 ≤ vi ≤ 2 × 104
Output

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

ExamplesInput
4
2 1 4 3
1 2 3 4
Output
4
Input
4
1 2 3 4
1 2 3 4
Output
10

加入题单

上一题 下一题 算法标签: