插入排序

题目描述

有 $N$ 个人，编号为 $1$ 到 $N$，从左到右排成一列。初始时，从左数第 $i$ 个人的编号为 $P_i$。

目标是通过反复执行以下三种操作，把人按编号从左到右升序排列。操作可以执行任意次数（可以为 0 次），顺序任意。

1. 选择整数 $i\ (1 \le i \le N)$，支付代价 $A_i$，把编号为 $i$ 的人移到任意位置。
2. 选择整数 $i\ (1 \le i \le N)$，支付代价 $B_i$，把编号为 $i$ 的人移到队列最左端。
3. 选择整数 $i\ (1 \le i \le 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$

输出格式

输出达成目标前所需支付的最小总代价。

样例

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

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le P_i \le N$
• $1 \le A_i, B_i, C_i \le 10^9$
• $P_i \neq P_j\ (i \neq j)$
• 输入均为整数