分数: 600 点
问题陈述
有 N 已获得 ID 号的人 1 通过 N,从左到右站成一排。最初,身份证号码 i左起第一个人是 P_i.
你的目标是通过重复执行以下三种操作,将人员按照 ID 号从左到右升序重新排列。您可以以任何顺序执行这些操作任意次数(可能为零)。
- 选择一个整数 i\ (1 \leq i \leq N),支付费用 A_i,并移动人 i (身份证号码为 i) 到您选择的任何位置。
- 选择一个整数 i\ (1 \leq i \leq N),支付费用 B_i,并移动人 i 到行的左端。
- 选择一个整数 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
示例输出 1
6
通过支付费用可以按照ID号从小到大的顺序重新排列人员 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
示例输出 2
15
以下操作顺序可最大限度地降低总成本:
- 支付费用 B_1=8 移动人员 1 到左端;
- 支付费用 C_5=5 移动人员 5 到右端;
- 支付费用 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
示例输出 3
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
示例输出 4
20637