AT_abc201_f [ABC201F] Insertion Sort

有 $N$ 个人，编号为 $1$ 到 $N$，他们从左到右排成一列。最初，从左起第 $i$ 个人的编号为 $P_i$。 你的目标是通过重复以下三种操作，使得所有人从左到右按编号升序排列。这些操作可以以任意顺序进行任意多次（也可以不进行）。 - 选择一个整数 $i\ (1 \leq i \leq N)$，支付代价 $A_i$，将第 $i$ 个人 (id 为 $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$

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

## 限制条件 - $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)$ - 所有输入均为整数 ## 样例解释 1 只需支付代价 $C_3=6$，将第 $3$ 个人移动到最右端，即可使所有人按升序排列。不存在比这更低的总代价，因此答案为 $6$。 ## 样例解释 2 按以下顺序操作可以达到最小总代价： - 支付代价 $B_1=8$，将第 $1$ 个人移动到最左端。 - 支付代价 $C_5=5$，将第 $5$ 个人移动到最右端。 - 支付代价 $C_6=2$，将第 $6$ 个人移动到最右端。 由 ChatGPT 4.1 翻译