問題文

N 個の箱と N 個のボールがあり、箱とボールにはそれぞれ 1 から N までの番号が付けられています。各箱はちょうど 1 個のボールが入る大きさであり、最初箱 i にはボール P_i が入っています。また箱は開閉することができ、最初すべての箱は閉じています。

これから 2 回の移動イベントが行われます。各イベントでは次の手順でボールを移動させます。

1. いくつかの箱を選んでその箱を開ける。箱を開けるには箱ごとに決まったコストがかかる。
2. 開いている箱の間でボールを自由に移動させる。ただし移動が終わったときすべての箱にちょうど 1 個のボールが入っていなければならない。
3. 開いている箱をすべて閉じる。

箱 i を開くのにかかるコストは、 1 度目のイベントにおいては A_i、2 度目のイベントにおいては B_i です。2 度の移動イベントを終えたときに箱 i にボール i が入っていなければなりません。かかるコストの合計の最小値を求めてください。

制約

• 1 \leq N \leq 10^5
• 1 \leq P_i \leq N
• i \neq j のとき P_i \neq P_j
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• 入力はすべて整数である。

入力例 1

5
2 4 5 1 3
11 5 3 3 8
4 6 7 9 3

出力例 1

28

1 度目の移動イベントにおいては箱 2 と 4 を開きボール 1 を箱 2 に、ボール 4 を箱 4 に移動します。これにはコストが 8 だけかかります。

2 度目の移動イベントにおいては箱 1 、 2 、 3 、5 を開き、ボール 1 、 2 、 3 、5 をそれぞれ目的の箱に移動させます。これにはコストが 20 だけかかります。

合計 28 のコストで条件を達成することができ、これが必要なコストの最小値になります。

入力例 2

1
1
1000000000
1000000000

出力例 2

0

すでに条件を満たしている場合もあります。