F - 插入排序

得分：600 分

问题描述

有 $N$ 个人，从左到右站成一排，他们的编号从 $1$ 到 $N$。初始时，第 $i$ 个人的编号是 $P_i$。

你的目标是将这些人按编号从小到大重新排列，通过以下三种操作来实现。你可以按照任意顺序，任意次数（也可以一次都不操作）执行这些操作。

1. 选择一个整数 $i$（$1 \leq i \leq N$），支付代价 $A_i$，将第 $i$ 个人（编号为 $i$ 的人）移到任意位置。
2. 选择一个整数 $i$（$1 \leq i \leq N$），支付代价 $B_i$，将第 $i$ 个人移到串列的最左边。
3. 选择一个整数 $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$

输出

输出你在实现目标之前需要支付的总代价的最小值。

样例

样例 1

输入：

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

输出：

6

你可以通过支付代价 $C_3=6$ 将第3个人移到末尾，将这些人按编号从小到大重新排列。没有更便宜的方法，因此答案就是 $6$。

样例 2

输入：

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

以下操作序列使总代价最小：

1. 支付代价 $B_1=8$，将第1个人移到最左边；
2. 支付代价 $C_5=5$，将第5个人移到最右边；
3. 支付代价 $C_6=2$，将第6个人移到最右边。

样例 3

输入：

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

样例 4

输入

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