配点 : $600$ 点

問題文

$1$ から $N$ までの番号が振られた $N$ 人の人が左右一列に並んでいます。はじめ、左から $i$ 番目の人の番号は $P_i$ です。

あなたの目標は、以下の $3$ 種類の操作を繰り返すことで人々が左から番号の昇順で並んでいるようにすることです。これらの操作は、任意の順に何回でも（$0$ 回でもよい）行うことができます。

• 整数 $i\ (1 \leq i \leq N)$ を選ぶ。コスト $A_i$ を払い、人 $i$ を好きな位置に移動させる。
• 整数 $i\ (1 \leq i \leq N)$ を選ぶ。コスト $B_i$ を払い、人 $i$ を左端に移動させる。
• 整数 $i\ (1 \leq i \leq N)$ を選ぶ。コスト $C_i$ を払い、人 $i$ を右端に移動させる。

目標を達成するまでに支払う合計コストを最小化してください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq P_i \leq N$
• $1 \leq A_i,B_i,C_i \leq 10^9$
• $P_i \neq P_j\ (i \neq j)$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_N$ $B_N$ $C_N$

出力

目標を達成するまでに支払う合計コストの最小値を出力せよ。

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

6

コスト $C_3=6$ を払って人 $3$ を右端に動かすことで、人々を昇順に並び替えることができます。

これより合計コストが低い並び替え方は存在しないので、答えは $6$ となります。

6
2 6 5 3 4 1
10 8 16
30 2 10
10 17 8
11 27 22
8 6 5
15 29 2

15

以下の順に操作を行うことで最小値を達成可能です。

• コスト $B_1=8$ を払い、人 $1$ を左端に移動させる。
• コスト $C_5=5$ を払い、人 $5$ を右端に移動させる。
• コスト $C_6=2$ を払い、人 $6$ を右端に移動させる。

9
3 8 4 7 6 9 1 5 2
7976 3696 9706
768 8807 8521
1133 8683 7120
1189 3331 2259
900 7451 1159
6126 2639 7107
5540 8253 2891
8417 4220 9091
8732 1417 1540

15865

12
11 9 1 12 2 7 3 5 10 4 6 8
3960 3158 9029
6521 6597 7581
5688 2299 2123
4946 4298 9122
394 4350 9142
3098 7151 2039
8525 3758 6155
6970 3658 9353
9780 1778 3608
6065 5562 923
9701 5524 6482
9395 6016 705

20637