问题 F: 新版移球游戏
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
桌子上现在有 $N$ 个球，从左到右第 $i$ 个球有一个编号 $P_i$ ，你需要移动某些球，使得球的编号是按从小到大排列的。
具体移动规则如下：
你可以花费 $A_i$ ，将编号为 $i$ 的球移动到任意地方。
你可以花费 $B_i$ ，将编号为 $i$ 的球移动到排列的最左端。
你可以花费 $C_i$ ，将编号为 $i$ 的球移动到排列的最右端。
求将原排列移动成按编号从小到大排列所需的最小花费。
具体移动规则如下：
你可以花费 $A_i$ ，将编号为 $i$ 的球移动到任意地方。
你可以花费 $B_i$ ，将编号为 $i$ 的球移动到排列的最左端。
你可以花费 $C_i$ ，将编号为 $i$ 的球移动到排列的最右端。
求将原排列移动成按编号从小到大排列所需的最小花费。
输入
$N$
$P_1$ $P_2$ $...$ $P_N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$...$
$A_N$ $B_N$ $C_N$
$1 \le N \le 2×10^5$
$1 \le P_i \le N$
$1 \le A_i,B_i,C_i \le 10^9$
$P_i$各不相等。
所有输入数据都是整数。
$P_1$ $P_2$ $...$ $P_N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$...$
$A_N$ $B_N$ $C_N$
$1 \le N \le 2×10^5$
$1 \le P_i \le N$
$1 \le A_i,B_i,C_i \le 10^9$
$P_i$各不相等。
所有输入数据都是整数。
输出
最小花费
样例输入 复制
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