题目描述

$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$ を右端に移動させる。

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

输入格式

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

$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$

输出格式

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

题目大意

$N$ 个人排成一列，他们的编号是 $1$ 到 $N$ 的排列。左起第 $i$ 个人的编号是 $P_i$。

你可以以任意次序进行任意多次下列操作：

• 选择一个人，设其编号为 $i$，支付 $A_i$ 的代价将其移动到任意位置。
• 选择一个人，设其编号为 $i$，支付 $B_i$ 的代价将其移动到最左端。
• 选择一个人，设其编号为 $i$，支付 $C_i$ 的代价将其移动到最右端。

其中 $A_i,B_i,C_i$ 由题目输入。

你的目标是使得所有人的编号从左至右递增。输出达成目标的最小代价。

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

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

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

提示

制約

• $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)$
• 入力は全て整数

Sample Explanation 1

コスト $C_3=6$ を払って人 $3$ を右端に動かすことで、人々を昇順に並び替えることができます。 これより合計コストが低い並び替え方は存在しないので、答えは $6$ となります。

Sample Explanation 2

以下の順に操作を行うことで最小値を達成可能です。 - コスト $B_1=8$ を払い、人 $1$ を左端に移動させる。 - コスト $C_5=5$ を払い、人 $5$ を右端に移動させる。 - コスト $C_6=2$ を払い、人 $6$ を右端に移動させる。